Enhancing MIP branching decisions by using the sample variance of pseudo-costs

Please always quote using this URN: urn:nbn:de:0297-zib-54591
  • 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 two-sample Student-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
Metadaten
Author:Gregor Hendel
Document Type:ZIB-Report
Tag:mixed-integer programming; reliability branching
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Date of first Publication:2015/04/21
Series (Serial Number):ZIB-Report (15-28)
ISSN:1438-0064
Published in:Appeared in: Integration of AI and OR Techniques in Constraint Programming. Lecture Notes in Computer Science 9075. 2015 pp. 199-214
Preprint:urn:nbn:de:0297-zib-54591
DOI:http://dx.doi.org/10.1007/978-3-319-18008-3_14

$Rev: 13581 $