Optimization Online


Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation

Daniel Anderson(dlanders***at***cs.cmu.edu)
Gregor Hendel(hendel***at***zib.de)
Pierre Le Bodic(pierre.lebodic***at***monash.edu)
Merlin Viernickel(viernickel***at***zib.de)

Abstract: We propose a simple and general online method to measure the search progress within the Branch-and-Bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed-Integer Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant. Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances. It is implemented in the MIP solver SCIP and will be available in future releases.

Keywords: mixed integer programming solvers; restarts; progress measures; tree-size estimates

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: accepted for publication in AAAI-19 proceedings. preprint published as ZIB-Report 19-11, Feb 19, Zuse Institute Berlin, Takustr 7, 14195 Berlin, Germany

Download: [PDF]

Entry Submitted: 02/27/2019
Entry Accepted: 02/27/2019
Entry Last Modified: 02/27/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society