Learning to Use Local Cuts
- We propose a machine learning approach to address a specific algorithmic question that arises during the solving process of a mixed-integer linear programming problem, namely, whether to use cutting planes only at the root node or also at internal nodes of the branch-and-bound search tree, or equivalently, whether to run a cut-and-branch or rather a branch-and-cut algorithm. Within a supervised regression framework, we develop three machine learning models, Linear Model, Random Forest and Neural Network, for predicting the relative performance between the two methods, local-cut and no-local-cut. Hence, through an extensive computational study conducted with FICO Xpress over a large test bed of problems, we evaluate the produced strategies, and we show that they are able to provide, upon the existing policies, a significant improvement to the performance of the solver. In fact, a variant of the random forest suggested in the present work has already been implemented by the development team of Xpress, and released with version 8.13 of the software.
Author: | Matteo FrancobaldiORCiD |
---|---|
Document Type: | Master's Thesis |
Tag: | Artificial Intelligence; Machine Learning; Mathematical Programming |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
CCS-Classification: | I. Computing Methodologies |
Granting Institution: | Freie Universität Berlin |
Advisor: | Timo Berthold, Ralf Borndörfer, Tim Conrad |
Year of first publication: | 2021 |