Learning to Use Local Cuts
From MaRDI portal
Publication:6402946
arXiv2206.11618MaRDI QIDQ6402946FDOQ6402946
Authors: Timo Berthold, Matteo Francobaldi, Gregor Hendel 
Publication date: 23 June 2022
Abstract: An essential component in modern solvers for mixed-integer (linear) programs (MIPs) is the separation of additional inequalities (cutting planes) to tighten the linear programming 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 costs, 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 performance 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.
Mixed integer programming (90C11) Software, source code, etc. for problems pertaining to operations research and mathematical programming (90-04)
This page was built for publication: Learning to Use Local Cuts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6402946)
