Enhancing MIP Branching Decisions by Using the Sample Variance of Pseudo Costs

  • The selection of a good branching variable is crucial for small search trees in Mixed Integer Programming. Most modern solvers employ a strategy guided by history information, mainly the variable pseudo-costs, which are used to estimate the objective gain. At the beginning of the search, such information is usually collected via an expensive look-ahead strategy called strong branching until variables are considered reliable. The reliability notion is thereby mostly based on fixed-number thresholds, which may lead to ineffective branching decisions on problems with highly varying objective gains. We suggest two new notions of reliability motivated by mathematical statistics that take into account the sample variance of the past observations on each variable individually. The first method prioritizes additional strong branching look-aheads on variables whose pseudo-costs show a large variance by measuring the relative error of a pseudo-cost confidence interval. The second method performs a specialized version of a two-sample Student’s t -test for filtering branching candidates with a high probability to be better than the best history candidate. Both methods were implemented in the MIP-solver SCIP and computational results on standard MIP test sets are presented.

Export metadata

  • Export Bibtex
Author:Gregor Hendel
Document Type:In Proceedings
Parent Title (English):Integration of AI and OR Techniques in Constraint Programming
First Page:199
Last Page:214
Series:Lecture Notes in Computer Science
Year of first publication:2015

$Rev: 13581 $