TY  - JOUR
U1  - Wissenschaftlicher Artikel
A1  - Berthold, Timo
A1  - Francobaldi, Matteo
A1  - Hendel, Gregor
T1  - Learning to use local cuts
JF  - Mathematical Programming Computation
N2  - An essential component in modern solvers for mixed-integer (linear) programs (MIPs)
is the separation of additional inequalities (cutting planes) to tighten the linear pro-
gramming relaxation. Various algorithmic decisions are necessary when integrating
cutting plane methods into a branch-and-bound (B&B) solver as there is always the
trade-off between the efficiency of the cuts and their overhead, given that they tend
to slow down the solution time of the relaxation. One of the most crucial questions
is: Should cuts only be generated globally at the root or also locally at nodes of the
tree? We address this question by a machine learning approach for which we train a
regression forest to predict the speed-up (or slow-down) provided by using local cuts.
We demonstrate with an open implementation that this helps to improve the perfor-
mance of the FICO Xpress MIP solver on a public test set of general MIP instances.
We further report on the impact of a practical implementation inside Xpress on a large,
diverse set of real-world industry MIPs.
AB  - An essential component in modern solvers for mixed-integer (linear) programs (MIPs)
is the separation of additional inequalities (cutting planes) to tighten the linear pro-
gramming relaxation. Various algorithmic decisions are necessary when integrating
cutting plane methods into a branch-and-bound (B&B) solver as there is always the
trade-off between the efficiency of the cuts and their overhead, given that they tend
to slow down the solution time of the relaxation. One of the most crucial questions
is: Should cuts only be generated globally at the root or also locally at nodes of the
tree? We address this question by a machine learning approach for which we train a
regression forest to predict the speed-up (or slow-down) provided by using local cuts.
We demonstrate with an open implementation that this helps to improve the perfor-
mance of the FICO Xpress MIP solver on a public test set of general MIP instances.
We further report on the impact of a practical implementation inside Xpress on a large,
diverse set of real-world industry MIPs.
Y1  - 2025
SN  - 1867-2949
SS  - 1867-2949
U6  - https://doi.org/10.1007/s12532-025-00278-y
DO  - https://doi.org/10.1007/s12532-025-00278-y
VL  - 17
IS  - 3
SP  - 437
EP  - 450
S1  - 14
PB  - Springer Science and Business Media LLC
ER  -