Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-4938
Main Title: Exact and fast algorithms for mixed-integer nonlinear programming
Translated Title: Exakte und schnelle Algorithmen für gemischt-ganzzahlige nichtlineare Programmierung
Author(s): Gleixner, Ambros M.
Advisor(s): Grötschel, Martin
Referee(s): Koch, Thorsten
Lodi, Andrea
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: Mixed-integer nonlinear programming (MINLP) comprises the broad class of finite-dimensional mathematical optimization problems from mixed-integer linear programming and global optimization. The combination of the two disciplines allows us to construct more accurate models of real-world systems, while at the same time it increases the algorithmic challenges that come with solving them. This thesis presents new methods that improve the numerical reliability and the computational performance of global MINLP solvers. Since state-of-the-art algorithms for nonconvex MINLP fundamentally rely on solving linear programming (LP) relaxations, we address numerical accuracy directly for LP by means of LP iterative refinement: a new algorithm to solve linear programs to arbitrarily high levels of precision. The thesis is supplemented by an exact extension of the LP solver SoPlex, which proves on average 1.85 to 3 times faster than current state-of-the-art software for solving general linear programs exactly over the rational numbers. These methods can be generalized to quadratic programming. We study their application to numerically difficult multiscale LP models for metabolic networks in systems biology. To improve the computational performance of LP-based MINLP solvers, we show how the expensive, but effective, bound-tightening technique called optimization-based bound tightening can be approximated more efficiently via feasibility-based bound tightening. The resulting implementation increases the number of instances that can be solved and reduces the average running time of the MINLP solver SCIP by 17-19% on hard mixed-integer nonlinear programs. Last, we present branching rules that exploit the presence of nonlinear integer variables, i.e., variables both contained in nonlinear terms and required to be integral. The new branching rules prefer integer variables when performing spatial branching, and favor variables in nonlinear terms when resolving integer infeasibility. They reduce the average running time of SCIP by 17% on affected instances. Most importantly, all of the new methods enable us to solve problems which could not be solved before, either due to their numerical complexity or because of limited computing resources.
Gemischt-ganzzahlige nichtlineare Programmierung (MINLP) umfasst die große Klasse endlichdimensionaler mathematischer Optimierungsprobleme aus der gemischt-ganzzahlig linearen Programmierung (MIP) und der globalen Optimierung nichtlinearer Programme (GO). Die Kombination beider Felder erlaubt eine genauere Modellierung vieler Anwendungsprobleme als mit nur einer der beiden Problemklassen möglich. Zugleich ergeben sich daraus aber neue algorithmische Herausforderungen bei der Lösung dieser Modelle. Die vorliegende Arbeit entwickelt neue Methoden zur Verbesserung der numerischen Stabilität und der Leistungsfähigkeit globaler MINLP-Löser. Da leistungsfähige Algorithmen in vielen modernen MINLP-Lösern auf linearer Programmierung (LP) basieren, behandeln wir numerische Genauigkeit direkt auf LP-Ebene. Dazu stellen wir ein neues iteratives Verfeinerungsverfahren für LP vor, das lineare Programme bis auf beliebige Genauigkeit lösen kann. Als Ergänzung zu dieser Arbeit wurde eine exakte Erweiterung des LP-Codes SoPlex entwickelt, die allgemeine lineare Programme mit rationalen Eingabedaten im Durchschnitt 1,85- bis 3-mal schneller löst als mit dem bisherigen Stand der Technik möglich. Wir zeigen, dass diese Algorithmen numerisch schwierige Multiskalenprobleme über metabolischen Netzwerken aus dem Gebiet der Systembiologie verlässlicher lösen als bisher unter Laufzeitbeschränkung möglich. Weiterhin verallgemeinern wir das iterative Verfeinerungsverfahren auf quadratische Programme. Zur Reduktion der Laufzeit LP-basierter MINLP-Löser zeigen wir, wie sich der Effekt des aufwändigen, aber effektiven Verfahrens Optimization-Based Bound Tightening durch das effizientere Feasibility-Based Bound Tightening annähern lässt. Daraus ergibt sich eine Implementierung, die die Anzahl gelöster Instanzen erhöht und die durchschnittliche Laufzeit des MINLP-Lösers SCIP um 17-19% auf schweren MINLPs reduziert. Darüber hinaus entwickeln wir Branching-Regeln, die das Vorhandensein nichtlinearer ganzzahliger Variablen ausnutzen, d.h. von Variablen, die sowohl ganzzahlige Werte annehmen müssen als auch in nichtlinearen Termen von Zielfunktion oder Nebenbedingungen enthalten sind. Dies führt zu einer durchschnittlichen Reduktion der Laufzeit des MINLP-Lösers SCIP um 17% auf relevanten Instanzen. Der wesentlichste Aspekt dieser Verbesserungen besteht jedoch darin, dass durch alle der entwickelten Methoden Probleminstanzen gelöst werden können, deren Lösung zuvor nicht möglich war, sei es aufgrund ihrer numerischen Komplexität oder wegen Beschränkungen an die verfügbare Rechenkapazität.
URI: http://depositonce.tu-berlin.de/handle/11303/5244
http://dx.doi.org/10.14279/depositonce-4938
Exam Date: 24-Jun-2015
Issue Date: 2015
Date Available: 13-Jan-2016
DDC Class: DDC::500 Naturwissenschaften und Mathematik::510 Mathematik::519 Wahrscheinlichkeiten, angewandte Mathematik
Subject(s): exact linear programming
iterative refinement
metabolic networks
optimization-based bound tightening (OBBT)
branching rules
exakte Lineare Programmierung
iterative Verfeinerung
metabolische Netzwerke
optimierungsbasierte Schrankenreduktion (OBBT)
Branching-Regeln
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
gleixner_ambros.pdf3,42 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.