On Efficient Solution Methods for Mixed-Integer Nonlinear and Mixed-Integer Quadratic Optimization Problems

Titelangaben

Lehmann, Thomas:
On Efficient Solution Methods for Mixed-Integer Nonlinear and Mixed-Integer Quadratic Optimization Problems.
Bayreuth , 2013 . - 249 S. S.
( Dissertation, 2013 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

Link zum Volltext (externe URL):

Abstract

In this thesis we focus on solution methods for convex mixed-integer nonlinear optimization problems (MINLP). As one main result, we propose a new algorithm guaranteeing global optimality for convex MINLPs under standard assumptions. The new algorithm called MIQP-supported outer approximation (MIQPSOA) incorporates the successive solution of convex mixed-integer quadratic programs (MIQP) in a linear outer approximation framework. An extensive numerical competitive study based on several different MINLP solvers shows, that a first implementation of the new method performs well in terms of both the reliability and the efficiency. Since the new method is designed to solve simulation-based optimization problems arising in practical engineering applications, the main performance criterion is the number of function evaluations required to solve a problem. Furthermore, the test results indicate, that the integration of mixed-integer search steps, resulting from the solution of convex MIQPs, significantly improves the reliability and the efficiency compared to well-known linear outer approximation methods. After reviewing available solution techniques for convex MINLP problems, we present the algorithmic set-up as well as the convergence proof of MIQPSOA. As pointed out in this dissertation, MIQPSOA is a first step towards a convergent MINLP solution method, that solely relies on the successive solution of convex MIQPs as proposed by Exler and Schittkowski. Finally, we present an extensive numerical test case study considering different solution methods for convex MINLPs. The second part of this thesis deals with efficient solution techniques for convex mixed-integer quadratic programs, that arise as subproblems during the solution of MINLPs by MIQP-based algorithms, such as MIQPSOA. First, we briefly review latest developments in state-of-the-art mixed-integer linear (MILP) solvers, since we want to develop a MIQP solver that incorporates the most successful components of MILP solvers. As we focus on branch-and-bound methods, one main component is an efficient and robust sub-solver for continuous quadratic programs, which is able to perform warmstarts. On the other hand, cutting planes have led to a tremendous speed-up of mixed-integer linear solvers during the last 20 years. As a consequence, we extend an efficient construction method for disjunctive cutting planes, such that it can be applied for MIQPs. Extensive numerical tests show, that the performance of a branch-and-bound solver can be significantly increased by exploiting warmstarts. Furthermore, it turns out, that in a majority of the test cases, where disjunctive cutting planes exist, the calculation times are reduced up to a factor of more than 5. Nevertheless there are also instances, where the presents of disjunctive cutting planes significantly slows down the performance. Due to the efficient cut generation method developed within this thesis, the generation of cutting planes has almost no influence on the calculation time, if no disjunctive cuts exist, which is the case in about 45 \% of all test instances. As a consequence, the application of cutting planes for MIQPs needs further attention and especially a dynamic cut management might be very profitable. Finally, we compare the performance of our branch-and-cut solver MIQL with the solver SCIP, which is one of the state-of-the-art MILP solvers, that can also solve MIQPs. These tests indicate, that MIQL outperforms SCIP on hard MIQP instances, while SCIP is faster for simpler test cases.

Abstract in weiterer Sprache

Im Fokus dieser Dissertation stehen Optimierungsverfahren für konvexe, gemischt-ganzzahlige, nichtlineare Optimierungsprobleme (MINLP). Ein wesentliches Resultat dieser Arbeit ist die Entwicklung eines neuen Lösungsverfahren. Dieser Algorithmus, der MIQP-supported Outer Approximation (MIQPSOA) genannt wird, garantiert globale Optimalität der Lösung unter üblichen Voraussetzungen. MIQPSOA basiert auf der sukzessiven Lösung von konvexen, gemischt-ganzzahligen, quadratischen Teilproblemen (MIQP) innerhalb eines Linear Outer Approximation Ansatzes. Eine aus-führliche numerische Studie mehrerer verschiedener MINLP-Lösungsverfahren zeigt, dass die erste Implementierung der neuen Methode sehr effizient und gleichzeitig robust ist. Da wir hauptsächlich simulations-basierte Optimierungsprobleme aus Anwendungen des Ingenieurswesens lösen, stellt die Anzahl der innerhalb des Lösungs-prozesses benötigten Funktionsauswertungen das wichtigste Performance-Kriterium dar. Die numerische Analyse zeigt, dass die Integration von gemischt-ganzzahligen Suchschritten, die aus der Lösung der MIQP-Teilprobleme bestimmt werden, sowohl die Robustheit als auch die Effizienz im Vergleich zum bekannten Verfahren der Linear Outer Approximation deutlich verbessert. Nachdem wir bekannte Verfahren zur Lösung von konvexen, gemischt-ganzzahligen, nichtlinearen Optimierungsproblemen vorgestellt haben, wird der Algorithmus MIQPSOA motiviert und beschrieben. Anschließend werden seine Konvergenzeigenschaften untersucht und Konvergenz für konvexe MINLPs bewiesen. Außerdem werden zu-künftige Verfahren skizziert, die Konvergenz für konvexe Probleme garantieren könnten und allein auf der sukzessiven Lösung von konvexen MIQPs basieren. Abschließend vergleichen wir die Performance und die Robustheit von verschiedenen MINLP Optimierungsverfahren. Der zweite Teil der Dissertation beschäftigt sich mit effizienten Lösungsverfahren für konvexe, gemischt-ganzzahlige, quadratische Optimierungsprobleme, die als Teilprobleme in MIQP-basierten Lösungsverfahren, wie beispielsweise MIQPSOA, auftreten. Ausgehend von einer kurzen Zusammenfassung der wichtigsten Entwicklungen bei aktuellen Lösungsverfahren für gemischt-ganzzahlig lineare Optimierungsprobleme (MILP), wird ein MIQP-Löser entwickelt. Dieser Löser namens MIQL beruht auf den wesentlichen Komponenten von aktuellen MILP-Lösungsverfahren. Da es sich bei MIQL um ein QP-basiertes Branch-and-bound Verfahren handelt, ist der effiziente und robuste Teilproblem-Löser für kontinuierliche quadratische Probleme von entscheidender Bedeutung. Besonders wichtig ist dabei die Fähigkeit, verwandte Probleme schnell mit sogenannten Warmstart-Methoden lösen zu können. Ein weiteres Hauptaugenmerk dieser Arbeit ist die Verwendung von allgemeinen Schnittebenen-Verfahren für nicht-basis Lösungen, wie sie bei der kontinuierlichen Relaxierung der MIQPs auftreten. Die Anwendung von Schnittebenen hat bei MILP-Lösern zu einer erheblichen Steigerung der Leistungsfähigkeit geführt, weshalb in dieser Dissertation erstmalig effiziente Konstruktionsverfahren für Schnittebenen entwickelt werden, die auch für MIQPs angewendet werden können. Eine ausführliche numerische Analyse zeigt, dass die Performance des Branch-and-bound Verfahrens durch Warmstarts signifikant verbessert werden kann. Weiterhin kann man feststellen, dass in der Mehrzahl der Fälle, in denen Schnittebenen des Types "disjunctive cutting planes" existieren, die Rechenzeiten deutlich, bis zu einem Faktor von mehr als 5, reduziert werden können. Trotzdem gibt es auch vereinzelte Instanzen, bei denen die Rechenzeit durch die Integration von disjunctive cutting planes stark erhöht wird. Das in dieser Dissertation entwickelte Schnittebenen-Verfahren selbst beeinflusst die Rechenzeit kaum. Dies ist besonders dann von Vorteil, falls keine disjuncitve cutting planes existieren, was bei der verwendeten Testbibliothek in circa 45 Prozent der Probleme der Fall ist. Zusammenfassend bleibt festzustellen, dass die Verwendung von Schnittebenen-Ver-fahren für MIQPs weitere Forschung notwendig macht und besonderes ein dynamisches Schnitt-ebenen-Management sehr profitabel erscheint. Im Vergleich zum Löser SCIP, der zu den besten Lösern für MILPs gehört und auch MIQPs lösen kann, stellt sich heraus, dass MIQL gerade bei schwierigen MIQP-Problemen deutlich überlegen ist.