90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Year of publication
- 2021 (1)
Document Type
- Master's Thesis (1)
Language
- English (1)
Has Fulltext
- yes (1) (remove)
Is part of the Bibliography
- no (1)
Keywords
- Machine Learning (1) (remove)
Institute
- AI in Society, Science, and Technology (1) (remove)
Learning to Use Local Cuts
(2021)
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.