Recovering beam search: enhancing the beam search approach for combinatorial optimization problems

Recovering beam search: enhancing the beam search approach for combinatorial optimization problems

0.00 Avg rating0 Votes
Article ID: iaor20043215
Country: Netherlands
Volume: 10
Issue: 1
Start Page Number: 89
End Page Number: 104
Publication Date: Jan 2004
Journal: Journal of Heuristics
Authors: , ,
Keywords: beam search
Abstract:

A hybrid heuristic method for combinatorial optimization problems is proposed that combines different classical techniques such as tree search procedures, bounding schemes and local search. The proposed method enhances the classic beam search approach by applying to each partial solution corresponding to a node selected by a beam, a further test that checks whether the current partial solution is dominated by another partial solution at the same level of the search tree. If this is the case, the latter solution becomes the new current partial solution. This step allows to partially recover from previous wrong decisions of the beam search procedure and can be seen as a local search step on the partial solution. We present here the application to two well known combinatorial optimization problems: the two-machine total completion time flow shop scheduling problem and the uncapacitated p-median location problem. In both cases the method strongly improves the performances with respect to the basic beam search approach and is competitive with the state of the art heuristics.

Reviews

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