Cyclic best first search: Using contours to guide branch-and-bound algorithms

David R. Morrison, Jason J. Sauppe, Wenda Zhang, Sheldon H. Jacobson, Edward C. Sewell

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)64-82
Number of pages19
JournalNaval Research Logistics
Volume64
Issue number1
DOIs
StatePublished - Feb 1 2017

Keywords

  • branch and bound
  • integer programming
  • optimization
  • search strategies

ASJC Scopus subject areas

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Cyclic best first search: Using contours to guide branch-and-bound algorithms'. Together they form a unique fingerprint.

Cite this