Cyclic best first search: Using contours to guide branch‐and‐bound algorithms |
| |
| Authors: | David R Morrison Jason J Sauppe Wenda Zhang Sheldon H Jacobson Edward C Sewell |
| |
| Affiliation: | 1. Yelp, San Francisco, CA;2. Department of Computer Science, University of Wisconsin‐La Crosse, La Crosse, WI;3. Department of Industrial and Systems Engineering, University of Illinois at Urbana‐Champaign, Urbana, IL;4. Department of Computer Science, University of Illinois at Urbana‐Champaign, Urbana, IL;5. Department of Mathematics and Statistics, Southern Illinois University Edwardsville, Edwardsville, IL |
| |
| Abstract: | The cyclic best‐first search (CBFS) strategy is a recent search strategy that has been successfully applied to branch‐and‐bound algorithms in a number of different settings. CBFS is a modification of best‐first search (BFS) that places search tree subproblems into contours which are collections of subproblems grouped in some way, and repeatedly cycles through all non‐empty contours, selecting one subproblem to explore from each. In this article, the theoretical properties of CBFS are analyzed for the first time. CBFS is proved to be a generalization of all other search strategies by using a contour definition that explores the same sequence of subproblems as any other search strategy. Further, a bound is proved between the number of subproblems explored by BFS and the number of children generated by CBFS, given a fixed branching strategy and set of pruning rules. Finally, a discussion of heuristic contour‐labeling functions is provided, and proof‐of‐concept computational results for mixed‐integer programming problems from the MIPLIB 2010 database are shown. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 64–82, 2017 |
| |
| Keywords: | branch and bound search strategies optimization integer programming |
|
|
