Adaptive solver behavior in mixed-integer programming

Autor: Hendel, Gregor Christian
Přispěvatelé: Koch, Thorsten, Technische Universität Berlin, Salvagnin, Domenico, Pokutta, Sebastian
Jazyk: angličtina
Rok vydání: 2022
Předmět:
DOI: 10.14279/depositonce-15958
Popis: This thesis addresses general-purpose solution techniques for mixed-integer programs (MIPs), a paradigm which captures formulations of countless real-world optimization problems. Most state-of-the-art MIP solvers employ a version of the branch-and-bound (B&B) algorithm to solve a MIP instance to proven optimality, supported by numerous auxiliary components that contribute new solutions or improve the dual convergence. One cannot expect that all such components are equally effective on all possible instances from the tremendous range of MIP applications. Ideally, a solver adapts to a given MIP instance by concentrating the available computational budget on those components that work best. In this thesis, we develop adaptive algorithmic behavior for several such MIP solver components solver as well as the B&B search itself. We develop new notions of pseudo-cost reliability, namely relative-error reliability and hypothesis reliability, by computing confidence intervals and pairwise t-tests on branching candidates to dynamically decide if strong branching is necessary. We develop two heuristic frameworks, adaptive large neighborhood search and adaptive diving that learn the most effective primal heuristics inspired by selection strategies for the multi-armed bandit problem. The presented ideas are transferred to adaptive LP pricing to maximize LP throughout by learning the pricing strategy for the dual simplex algorithms online during the search. Our proposed adaptive algorithmic behavior extends beyond individual solving components to the B&B search as a whole. To this end, we partition the B&B search into a feasibility phase, an improvement phase, and a heuristically detected proof phase. We improve solver performance by emphasizing different components and search strategies in each phase. We propose new estimation techniques for the progress of the B&B search based on forecasting and machine learning techniques. We turn this tree-size estimation into a novel restart strategy of the B&B algorithm called clairvoyant. As a methodological contribution, we describe the selection process of MIPLIB 2017, which is the current state-of-the-art library for benchmarking MIP solver performance. All of the discussed algorithmic approaches are evaluated within the MIP solver SCIP, for which they show clear performance benefits. They are publicly available as part of SCIP and have been adopted by state-of-the-art commercial solvers such as FICO Xpress.
Im Rahmen dieser Arbeit befassen wir uns mit anwendungsunabhängigen Lösetechniken für gemischt-ganzzahlige Optimierungsprobleme (engl. mixed-integer programs (MIPs)), ein Paradigma mit unzähligen praktischen Anwendungsbeispielen. Moderne Lösertechnologie basiert zumeist auf dem Branch-and-Bound-(B&B)-Algorithmus, welcher auf algorithmische Hilfskomponenten zur schnelleren Lösungsfindung und der Konvergenz der dualen Schranke angewiesen ist. Die Vielfalt an Anwendungsgebieten für MIP lässt schon erwarten, dass nicht alle B&B-Komponenten gleichermaßen erfolgreich auf allen erdenklichen MIP-Anwendungsgebieten sind. Idealerweise passt sich ein MIP-Löser zur Laufzeit an eine gegebene Instanz an, indem er eine bestmögliche Verteilung des zur Verfügung stehenden Budgets auf die einzelnen Komponenten erlernt. Im Rahmen dieser Arbeit werden neue adaptive Lernverfahren sowohl für einzelne Komponenten als auch für den B&B-Algorithmus vorgestellt. Die neu vorgestellten Entwicklungen in dieser Arbeit umfassen - verallgemeinerte Pseudokostenzuverlässigkeitsbestimmungen anhand von Konfidenzintervallen und statistischer Tests zur dynamischen Entscheidung, ob Strong Branching erforderlich ist, - heuristische Frameworks Adaptive Large Neighborhood Search und Adaptive Diving mit dem Ziel, die effektivsten Primalheuristiken im Laufe des Löseprozesses zu erlernen, - Adaptive LP Pricing zur Verbesserung des Knotendurchsatzes während der B&B-Suche durch dynamische Wahl der besten Pricing-Strategie für das Simplexverfahren, - eine Einteilung des Löseprozesses in drei Phasen: eine Zulässigkeits-, eine Verbesserungs-, und eine Beweisphase, und die Ausnutzung von Phaseninformation zur gezielten Steuerung des B&B-Verfahrens. - eine Abschätzung der verbleibenden Baumgröße und des Fortschritts des B&B-Verfahrens basierend auf Forecasting-Techniken und Methoden des Maschinellen Lernens. - die anschließende Ausnutzung dieser Schätzverfahren für Clairvoyant Restarts der B&B-Suche bei einer pessimistischen Prognose. Ein weiterer, methodischer Beitrag besteht in der detaillierten Vorstellung des Auswahlverfahrens der MIPLIB 2017, dem derzeitigen Standardbenchmarkset zur Evaluierung von MIP-Lösern. Alle neu vorgestellten Algorithmen wurden im Rahmen dieser Arbeit in den nichtkommerziellen MIP-Löser SCIP integriert und auch praktisch anhand von Rechenexperimenten ausgewertet. Sie sind somit als Teil von SCIP 7.0 öffentlich verfügbar, und wurden teilweise bereits in kommerzielle Löser wie FICO Xpress integriert.
Databáze: OpenAIRE
Externí odkaz: