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

Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products

  • The reformulation-linearization technique (RLT) is a prominent approach to constructing tight linear relaxations of non-convex continuous and mixed-integer optimization problems. The goal of this paper is to extend the applicability and improve the performance of RLT for bilinear product relations. First, a method for detecting bilinear product relations implicitly contained in mixed-integer linear programs is developed based on analyzing linear constraints with binary variables, thus enabling the application of bilinear RLT to a new class of problems. Our second contribution addresses the high computational cost of RLT cut separation, which presents one of the major difficulties in applying RLT efficiently in practice. We propose a new RLT cutting plane separation algorithm which identifies combinations of linear constraints and bound factors that are expected to yield an inequality that is violated by the current relaxation solution. A detailed computational study based on implementations in two solvers evaluates the performance impact of the proposed methods.

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Ksenia BestuzhevaORCiD, Ambros GleixnerORCiD, Tobias AchterbergORCiD
Dokumentart:Konferenzbeitrag
Titel des übergeordneten Werkes (Englisch):Integer Programming and Combinatorial Optimization. IPCO 2023.
Band:13904
Erste Seite:14
Letzte Seite:28
Serie:Lecture Notes in Computer Science
Verlag:Springer, Cham
Jahr der Erstveröffentlichung:2023
DOI:https://doi.org/10.1007/978-3-031-32726-1_2
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.