Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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.

Download full text files

Export metadata

Author:Matteo FrancobaldiORCiD
Document Type:Master's Thesis
Tag:Artificial Intelligence; Machine Learning; 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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.