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

Cutting Plane Selection with Analytic Centers and Multiregression

  • Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Mark Turner, Timo BertholdORCiD, Mathieu BesançonORCiD, Thorsten Koch
Document Type:In Proceedings
Parent Title (English):Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2023.
First Page:52
Last Page:68
Series:Lecture Notes in Computer Science
Date of first Publication:2023/05/23
Page Number:16
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.