Exact and fast algorithms for mixed-integer nonlinear programming

dc.contributor.advisorGrötschel, Martin
dc.contributor.authorGleixner, Ambros M.
dc.contributor.grantorTechnische Universität Berlinen
dc.contributor.refereeKoch, Thorsten
dc.contributor.refereeLodi, Andrea
dc.date.accepted2015-06-24
dc.date.accessioned2016-01-13T10:56:49Z
dc.date.available2016-01-13T10:56:49Z
dc.date.issued2015
dc.description.abstractMixed-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.en
dc.description.abstractGemischt-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.de
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/5244
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-4938
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc519 Wahrscheinlichkeiten, angewandte Mathematikde
dc.subject.otherexact linear programmingen
dc.subject.otheriterative refinementen
dc.subject.othermetabolic networksen
dc.subject.otheroptimization-based bound tightening (OBBT)en
dc.subject.otherbranching rulesen
dc.subject.otherexakte Lineare Programmierungde
dc.subject.otheriterative Verfeinerungde
dc.subject.othermetabolische Netzwerkede
dc.subject.otheroptimierungsbasierte Schrankenreduktion (OBBT)de
dc.subject.otherBranching-Regelnde
dc.titleExact and fast algorithms for mixed-integer nonlinear programmingen
dc.title.translatedExakte und schnelle Algorithmen für gemischt-ganzzahlige nichtlineare Programmierungde
dc.typeDoctoral Thesisen
dc.type.versionacceptedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
gleixner_ambros.pdf
Size:
3.34 MB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
5.75 KB
Format:
Item-specific license agreed upon to submission
Description:

Collections