Bayesian stopping rules for greedy randomized procedures

Bayesian stopping rules for greedy randomized procedures

0.00 Avg rating0 Votes
Article ID: iaor20071460
Country: Netherlands
Volume: 36
Issue: 3
Start Page Number: 365
End Page Number: 377
Publication Date: Nov 2006
Journal: Journal of Global Optimization
Authors: ,
Keywords: heuristics
Abstract:

A greedy randomized adaptive search procedure (GRASP) is proposed for the approximate solution of general mixed binary programming problems (MBP). Examples are provided of practical applications that can be formulated as MBP requiring the solution of a large number of problem instances. This justifies, from both a practical and a theoretical perspective, the development of stopping rules aimed at controlling the number of iterations in a GRASP. To this end, a Bayesian framework is laid down, two different prior distributions are proposed and stopping conditions are explicitly derived in analytical form. Numerical evidence shows that the stopping rules lead to an optimal trade-off between accuracy and computational effort, saving from unneeded iterations and still achieving good approximations.

Reviews

Required fields are marked *. Your email address will not be published.