5459
eng
reportzib
0
--
2015-04-21
--
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 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.
1438-0064
10.1007/978-3-319-18008-3_14
urn:nbn:de:0297-zib-54591
Appeared in: Integration of AI and OR Techniques in Constraint Programming. Lecture Notes in Computer Science 9075. 2015 pp. 199-214
urn:nbn:de:0297-zib-54591
Gregor Hendel
Gregor Hendel
ZIB-Report
15-28
eng
uncontrolled
mixed-integer programming
eng
uncontrolled
reliability branching
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Hendel, Gregor
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5459/paper.pdf