Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 10 von 17
Zurück zur Trefferliste

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.

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Mark Turner, Timo BertholdORCiD, Mathieu BesançonORCiD, Thorsten Koch
Dokumentart:Konferenzbeitrag
Titel des übergeordneten Werkes (Englisch):Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2023.
Band:13884
Erste Seite:52
Letzte Seite:68
Serie:Lecture Notes in Computer Science
Verlag:Springer
Datum der Erstveröffentlichung:23.05.2023
Seitenzahl:16
Preprint:urn:nbn:de:0297-zib-89065
DOI:https://doi.org/10.1007/978-3-031-33271-5_4
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.