Article ID: | iaor20084086 |
Country: | Netherlands |
Volume: | 156 |
Issue: | 1 |
Start Page Number: | 129 |
End Page Number: | 141 |
Publication Date: | Dec 2007 |
Journal: | Annals of Operations Research |
Authors: | Prestwich Steven |
Keywords: | programming: branch and bound |
Branch-and-bound uses relaxation to prune search trees but sometimes scales poorly to large problems. Conversely, local search often scales well but may be unable to find optimal solutions. Both phenomena occur in the construction of low-autocorrelation binary sequences (LABS), a problem arising in communication engineering. This paper proposes a hybrid approach to optimization: using relaxation to prune local search spaces. An implementation gives very competitive results, showing the feasibility of the approach.