Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-9889
For citation please use:
Main Title: Tighter relaxations in mixed-integer nonlinear programming
Translated Title: Stärkere Relaxierungen in gemischt-ganzzahliger nichtlinearer Programmierung
Author(s): Müller, Benjamin
Advisor(s): Koch, Thorsten
Referee(s): Koch, Thorsten
Lodi, Andrea
Pfetsch, Marc
Granting Institution: Technische Universität Berlin
Type: Doctoral Thesis
Language Code: en
Abstract: Mixed-integer nonlinear programming (MINLP) is one of the most important classes of mathematical optimization problems that combines difficulties from mixed-integer linear programming and nonlinear programming, namely optimizing over a set that is described by integrality, linear, and nonlinear restrictions. This class of optimization problems is essential when constructing accurate models of real-world applications such as energy production and distribution, logistics, engineering design, manufacturing, and fields in chemical and biological sciences. To the best of our knowledge, all state-of-the-art algorithms for solving nonconvex MINLPs to global optimality are based on branch and bound. The performance of these algorithms mainly depends on tight relaxations of a MINLP that are refined throughout a tree search. For this reason, the contribution of this thesis is to present new methods to construct and strengthen relaxations for mixed-integer nonlinear programs. One application of MINLP is the recursive circle packing problem (RCPP), which arises in the tube industry when packing pipes into rectangular containers. Solving a compact formulation for the RCPP is entirely out of reach for state-of-the-art MINLP solvers because relaxations for this problem are known to be weak. To construct significantly tighter relaxations, we present an exact reformulation of the RCPP that is based on a Dantzig-Wolfe decomposition of a nonconvex MINLP formulation. We use column generation techniques to design an algorithm that solves the continuous relaxation of the reformulation to global optimality. This relaxation is substantially tighter than relaxations for a compact MINLP formulation, which enables us to solve 287 out of 800 instances to global optimality that could not be solved so far. The most fundamental ingredient in MINLP solvers is the well-known McCormick relaxation for a product of two variables x and y over a box-constrained domain. This relaxation is far from being tight if the feasible region of a MINLP and its convexification projected in the x-y-space is a strict subset of the box. We develop an algorithm that solves a sequence of linear programs to compute globally valid inequalities on x and y in a similar fashion as optimization-based bound tightening. These valid inequalities enable us to exploit polyhedral results from the literature to tighten the classic McCormick relaxation. Additionally, we present two novel propagation algorithms that compute stronger bounds for x, y, and xy. The resulting implementation reduces the average running time by 36% on difficult MINLPs. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solvers improved tremendously during the last decades and are nowadays able to solve problems with a moderate presence of nonconvexities. This progress opens the door for the use of potentially tighter relaxations that contain only a few nonconvexities. Such a nonconvex relaxation can be obtained via the aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in a MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm in the literature that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm’s ability to generate tight relaxations through extensive computational experiments. Our results show that we are able to improve the best known bounds for unsolved instances and decrease the average gap by a factor of two on difficult instances. Finally, we present the concept of variable holes for nonconvex MINLPs. Due to the presence of nonconvex nonlinear constraints, the set of feasible assignments of a variable can be disconnected. The resulting forbidden regions are called variable holes and can be viewed as a generalization of integrality restrictions. By exploiting these holes, it is possible to strengthen the relaxation of a MINLP by applying techniques that have been exclusively developed for integer variables to continuous variables. Unfortunately, computing a variable hole is in general NP-hard. Still, for many MINLPs, it is enough to consider relaxations that are described by few constraints to detect variable holes. Based on this observation, we develop three algorithms that are capable of computing variable holes for practical instances. Our computational study shows that integrating variable holes into pseudo cost branching rules decreases the average running time by 62% on affected instances.
Gemischt-ganzzahlige nichtlineare Programmierung (MINLP) ist eine der bedeutendsten Klassen mathematischer Optimierungsprobleme. Sie verbindet Schwierigkeiten von gemischt-ganzzahliger linearer Programmierung und nichtlinearer Programmierung, nämlich die Optimierung einer linearen Funktion über eine Menge, die durch ganzzahlige, lineare- und nichtlineare Bedingungen beschrieben ist. Diese Klasse von Optimierungsproblemen ist unabdingbar, wenn akkurate mathematische Modelle realer Anwendungen im Bereich Energieerzeugung und -verteilung, Logistik, Konstruktion, Fertigung und in chemischen und biologischen Prozessen benötigt werden. Algorithmen zur Lösung dieser nicht konvexen Optimierungsproblemen, die globale Optimalität garantieren, basieren auf dem branch-and-bound Verfahren. Die Performanz dieses Verfahrens hängt wesentlich von der Stärke von Relaxierungen ab, die während einer Baumsuche verfeinert werden. In dieser Arbeit werden neue Methoden präsentiert, um stärkere Relaxierungen für gemischt-ganzzahlige nichtlineare Optimierungsprobleme zu berechnen. Eine wichtige Anwendung von MINLP ist das recursive circle packing problem (RCPP), das in der Rohrindustrie beim Verpacken von Rohren in rechteckige Container auftritt. Das Lösen einer kompakten nichtlinearen Formulierung ist für aktuelle Löser nicht in annehmbarer Zeit möglich, weil die Qualität der konstruierten Relaxierungen für diese Art von Optimierungsproblemen schwach sind. Um signifikant stärkere Relaxierungen zu konstruieren, präsentieren wir eine exakte Reformulierung des RCPPs, die auf einer Dantzig-Wolfe Zerlegung einer kompakten nichtlinearen Formulierung basiert. Wir benutzen einen Spaltengenerierungsansatz zum Lösen der kontinuierlichen Relaxierung der neuen Formulierung. Die Qualität der Relaxierung ist wesentlich stärker als die Relaxierung einer kompakten Formulierung und ermöglicht uns erstmals 287 von 800 ungelösten Instanzen zur globalen Optimalität zu lösen. Eine der grundlegendsten Komponenten von MINLP Lösern ist die bekannte McCormick Relaxierung für ein Produkt aus zwei Variablen x und y über eine rechteckige Box. Diese Relaxierung ist alles andere als optimal, wenn die Menge der zulässigen Punkte von x und y eine strikte Teilmenge der rechteckigen Box ist. Baiserend auf dem Lösen von linearen Programmen entwickeln wir einen Algorithmus der gültige Ungleichungen für x und y berechnet. Diese Ungleichungen erlauben es uns, Methoden aus der Literatur zu verwenden, um die McCormick Relaxierung zu verbessern. Zusätzlich präsentieren wir zwei neue Propagierungsalgorithmen, um stärkere Schranken für x, y und xy zu berechnen. Unsere Implementierung reduziert die mittlere Laufzeit um 36% auf schwierigen Instanzen. Sowohl aus theoretischen als auch aus praktischen Gründen sind Relaxierungen für nicht konvexe Optimierungsprobleme konvex. Gleichwohl können durch die stetigen Verbesserung der letzten Jahrzehnte aktuelle Löser heutzutage Probleme mit einer moderaten Anzahl von Nichtkonvexitäten lösen. Dieser Fortschritt erlaubt es uns nicht konvexe, aber signifikant stärkere Relaxierungen zu benutzen. Ein Beispiel für eine solche Relaxierung ist die surrogate Relaxierung, die auf dem Aggregieren von Bedingungen basiert. Diese Art von Relaxierung wurde in den 70er und 80er Jahren intensiv studiert, aber seitdem nur selten betrachtet. Wir greifen surrogate Relaxierungen wieder auf und zeigen, welche Vor- und Nachteile diese für das Lösen nichtlinearer Optimierungsprobleme haben. Zusätzlich präsentieren wir den ersten Algorithmus zur Berechnung der besten verallgemeinerten surrogate Relaxierung, die mehrere Aggregierungsbedingungen erlaubt. Wir präsentieren eine Vielzahl von Verbesserungen für die Performanz unseres Algorithmus und evaluieren durch umfangreiche Experimente, wie stark die berechneten surrogate Relaxierungen sind. Unsere Rechenergebnisse zeigen, dass unser Algorithmus die best bekannte untere Schranke einiger ungelöster Instanzen verbessern kann und im Mittel die Wurzellücke um einen Faktor von zwei auf schwierigen Instanzen reduziert. Zuletzt stellen wir das Konzept der Variablenlöcher für nicht konvexe Optimierungsprobleme vor. Aufgrund von nicht konvexer nichtlinearer Bedingungen kann die Menge der möglichen zulässigen Punkte für eine Variablen in mehrere Intervalle zerfallen. Die resultierenden nicht zulässigen Bereiche werden als Variablenlöcher bezeichnet, welche eine Verallgemeinerung von Ganzzahligkeitsbedingungen sind. Durch das Verwenden dieser Löcher ist es möglich Relaxierungen für nicht konvexe Optimierungsprobleme zu verbessern, indem Methoden aus der Literatur für ganzzahlige Variablen auf Variablen mit Variablenlöchern übertragen werden. Obwohl das Berechnen von Variablenlöchern NP-schwer ist, präsentieren wir drei Algorithmen, die für praxisrelevante Instanzen Variablenlöcher berechnen können. Wir zeigen, dass die Integration von Variablenlöchern in Pseudokosten-basierten Branchingregeln die mittlere Laufzeit um 62% auf beeinflusste Instanzen reduziert.
URI: https://depositonce.tu-berlin.de/handle/11303/10997
http://dx.doi.org/10.14279/depositonce-9889
Exam Date: 18-Mar-2020
Issue Date: 2020
Date Available: 11-May-2020
DDC Class: 510 Mathematik
Subject(s): mixed-integer nonlinear programming
nonconvex
global optimization
relaxations
gemischt-ganzzahlige nichtlineare Programmierung
nichtkonvex
globale Optimierung
Relaxierungen
License: https://creativecommons.org/licenses/by-sa/4.0/
Appears in Collections:Inst. Mathematik » Publications

Files in This Item:
mueller_benjamin.pdf
Format: Adobe PDF | Size: 34.39 MB
DownloadShow Preview
Thumbnail

Item Export Bar

This item is licensed under a Creative Commons License Creative Commons