Cyclic best first search: Using contours to guide branch‐and‐bound algorithms
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
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Feb 01, 2017
- Source ID
- 10.1002/nav.21732
Entities
People
- David R. Morrison
- Edward C. Sewell
- Jason J. Sauppe
- Sheldon H. Jacobson
- Wenda Zhang
Organizations
- Air Force Office of Scientific Research
- National Science Foundation
- Southern Illinois University
- United States Department of Defense
- University of Illinois Urbana–Champaign
- University of Wisconsin–La Crosse
- Yelp