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

Cutting Plane Selection with Analytic Centers and Multiregression

Please always quote using this URN: urn:nbn:de:0297-zib-89065
  • 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.

Download full text files

  • ZIB-Reporteng

    Cutting Plane Selection with Analytic Centers and Multiregression - Preprint

Export metadata

Author:Mark TurnerORCiD, Timo BertholdORCiD, Mathieu BesançonORCiD, Thorsten KochORCiD
Document Type:ZIB-Report
Tag:anlalytic center; cut selection; mixed-integer programming
Date of first Publication:2022/12/15
Series (Serial Number):ZIB-Report (22-28)
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.