Cutting plane selection for mixed-integer linear programming
Creators: name: Turner, Mark Ruben
Publisher: name: Technische Universität Berlin
Year: 2024
Subjects: subject: 500 Naturwissenschaften und Mathematik::510 Mathematik::519 Wahrscheinlichkeiten, angewandte Mathematik
subject: mixed-integer programming
subject: cutting planes
subject: cut selection
subject: machine learning

description: Mixed-Integer Linear Programming (MILP) is a ubiquitous and practical modelling paradigm that is essential for optimising a broad range of real-world systems. The backbone of all modern MILP solvers is the branch-and-cut algorithm, which is a hybrid of the branch-and-bound and cutting planes algorithms. Cutting planes (cuts) are linear inequalities that tighten the relaxation of a MILP. While a lot of research has gone into deriving valid cuts for MILPs, less emphasis has been put on determining which cuts to select. Cuts in general are generated in rounds, and a subset of the generated cuts must be added to the relaxation. The decision on which subset of cuts to add is called cut selection. This is a crucial task since adding too many cuts makes the relaxation large and slow to optimise over. Conversely, adding too few cuts results in an insufficiently tightened relaxation, and more relaxations need to be enumerated. To further emphasise the difficulty, the effectiveness of an applied cut is both dependent on the other applied cuts, and the state of the MILP solver. In this thesis, we present theoretical results on the importance and difficulty of cut selection, as well as practical results that use cut selection to improve general MILP solver performance. Improving general MILP solver performance is of great importance for practitioners and has many runoff effects. Reducing the solve time of currently solved systems can directly improve efficiency within the application area. In addition, improved performance enables larger systems to be modelled and optimised, and MILP to be used in areas where it was previously impractical due to time restrictions. Each chapter of this thesis corresponds to a publication on cut selection, where the contributions of this thesis can naturally be divided into four components. The first two components are motivated by instance-dependent performance. In practice, for each subroutine, including cut selection, MILP solvers have adjustable parameters with hard-coded default values. It is ultimately unrealistic to expect these default values to perform well for every instance. Rather, it would be ideal if the parameters were dependent on the given instance. To show this motivation is well founded, we first introduce a family of parametric MILP instances and cuts to showcase worst-case performance of cut selection for any fixed parameter value. We then introduce a graph neural network architecture and reinforcement learning framework for learning instance-dependent cut scoring parameters. In the following component, we formalise language for determining if a cut has theoretical usefulness from a polyhedral point of view in relation to other cuts. In addition, to overcome issues of infeasible projections and dual degeneracy, we introduce analytic center based distance measures. We then construct a lightweight multi-output regression model that predicts relative solver performance of an instance for a set of distance measures. The final two components are motivated by general MILP solver improvement via cut selection. Such improvement was shown to be possible, albeit difficult to achieve, by the first half of this thesis. We relate branch-and-bound and cuts through their underlying disjunctions. Using a history of previously computed Gomory mixed-integer cuts, we reduce the solve time of SCIP over the 67% of affected MIPLIB 2017 instances by 4%. In the final component, we introduce new cut scoring measures and filtering methods based on information from other MILP solving processes. The new cut selection techniques reduce the solve time of SCIP over the 97% of affected MIPLIB 2017 instances by 5%.
description: Gemischt-Ganzzahlige Lineare Programmierung (Mixed Integer Linear Programming, MILP) ist ein allgegenwärtiges und praktisches Modellierungsparadigma, welches eine essentielle Grundlage für die Optimierung vieler realer Systeme bildet. Das Rückgrat von allen modernen MILP Lösern ist der Branch-and-Cut Algorithmus, welcher eine Kombination des Branch-and-Bound Algorithmus und des Schnittebenenverfahrens darstellt. Schnittebenen (cutting plans oder kurz cuts) sind lineare Ungleichungen, welche die Relaxation eines MILPs verschärfen. Während sich eine Vielzahl an Forschungarbeiten im MILP Bereich mit der Berechnung valider Schnittebenen beschäftig hat, ist die Auswahlentscheidung der letztendlich zu nutzende Schnittebenen bisher nur wenig betrachtet worden. Schnittebenen werden im Allgemeinen in mehreren Runden erzeugt, um anschließend eine Teilmenge der generierten Schnittebenen zur Relaxation hinzuzufügen. Das hierbei zu lösende Problem der Schnittebenenauswahl (cut selection) ist von entscheidender Bedeutung für den Lösungsprozess. Werden der Relaxation zuviele Schnittebenen hinzugefügt wird sie zu groß und lässt sich nicht mehr effizient lösen. Andererseits bedeuten zu wenige Schnittebenen eine nicht ausreichende Verschärfung der Relaxation, wodurch mehr Branch-and-Bound Knoten betrachtet werden müssen. Dass die Effektivität einer Schnittebene sowohl von den anderen ausgewählten Schnittebenen als auch vom aktuellen Zustand des MILP Lösers abhängt, erschwert das Auswahlproblem zusätzlich. Die Ergebnisse dieser Arbeit umfassen sowohl theoretische Erkenntnisse zur Wichtigkeit und Schwierigkeit des Problems der Schnittebenenauswahl als auch praktische Resultate, welche die allgemeine Leistung von MILP Lösern mit Hilfe von Verfahren zur Schnittebenenauswahl verbessern. Gerade die allgemeine Leistungsverbesserung von MILP Lösern ist von enormer Wichtigkeit für praktische Anwendungen. Zum einen kann eine kürzere Lösungszeit von aktuell lösenbaren Problemen zu einer erhöhten Effizienz im jeweiligen Anwendungsgebiet beitragen. Zum anderen führt die allgemeine Leistungsverbesserung dazu, dass größere Probleme modelliert und gelöst werden können. So kann MILP in Bereichen genutzt werden, für die eine Anwendung auf Grund von Laufzeiteinschränkungen bisher nicht möglich war. Jedes Kapitel dieser Arbeit entspricht einer Veröffentlichung zum Schnittebenenauswahlproblem. Die Beiträge der Arbeit lassen sich dabei in vier Teilbereiche aufgliedern. Die ersten beiden Bereiche befassen sich mit instanzabhängiger Leistungsverbesserung eines MILP Lösers. Üblicherweise haben Löser änderbare Parameter, durch die sich das Verhalten der verschiedenen Subroutinen, wie zum Beispiel der Schnittebenenauswahl, anpassen lässt. Die Parameter haben voreingestellte Standardwerten, welche jedoch erwartbarerweise nicht für jede zu lösende Instanz die bestmögliche Wahl sind. Vielmehr wäre eine instanzabhängige Anpassung dieser Parameter ideal. Zur Unterstützung diese motivierende Aussage werden zunächst Familien von parametrisierten MILP Instanzen und entsprechende Schnittebenen vorgestellt, für die ein Worst-Case Verhalten der Schnittebenenauswahl für jeden fixierten Parameterwert gezeigt werden kann. Anschließend wird eine Architektur basierend auf graph-neuronalen Netzwerken (graph neural networks) sowie ein Modell für bestärkendes Lernen (reinforcement learning) vorgestellt, mit welchen instanzabhängige Parameter zur Bewertung von Schnittebenen erlernt werden können. Im nachfolgenden Teilbereich, werden formale Konzepte erstellt um den theoretischen polyedrischen Nutzen einer Schnittebene im Verhältnis zu anderen Schnittebenen beschreiben zu können. Außerdem wird ein Abstandmaß basierend auf dem analytischen Zentrum eingeführt um Probleme mit unzulässigen Projektionen und dualer Degeneration zu beheben. Abschließend wird ein einfaches Multi-Output-Regressionsmodell konstruiert, welches die relative Leistung eine Lösers auf einer Instanz für eine Menge an Abstandmaßen vorhersagt. Die verbleiben beiden Teilbereiche der Arbeit beschäftigen sich mit der allgemeiner Leistungsverbesserung von MILP Lösern mit Hilfe der Schnittebenenauswahl. Das eine solche Verbesserung zwar schwierig zu erreichen, jedoch prinzipiell möglich ist, wurde bereits in den zwei ersten Teilbereichen der Arbeit gezeigt. Es wird ein Verfahren präsentiert, welches die Erkenntnisse der Bewertung von historischen gemischt-ganzzahligen Gomory-Schnittebenen für die Auswahl des nächsten zu lösenden Branch-and-Bound Knotens nutzt. Durch die Verwendung dieses Verfahrens konnte die Lösungszeit von SCIP auf den betroffenen 67% der Instanzen der MIPLIB 2017 um 4% reduziert werden. Im letzte Teilbereich werde neue Maße zur Bewertung von Schnittebenen vorgestellt. Zusätzlich werden Filtermethoden entwickelt, welche auf bereitgestellten Daten der anderen MILP Löserbestandteile basieren. Dieses neue Verfahren zur Schnittebenenauswahl führt zur einer Reduzierung der Lösungszeit von SCIP auf den betroffenen 97% der Instanzen der MIPLIB 2017 um 5%.