Relaxation refinement for mixed-integer nonlinear programs with applications in engineering

Abstract

Lösungsstrategien für Gemischt-Ganzzahlige Nichtlineare Programme (MINLPs) basieren häufig auf einer konvexen Relaxierung der zulässigen Menge. Diese Relaxierung wird benutzt um untere Schranken zu ermitteln und um die Qualität lokaler Lösungen zu beurteilen. In dieser Thesis diskutieren wir verschiedene Ansätze um geeignete Relaxierungen zu konstruieren und zu verbessern. Außerdem analysieren wir diese in Hinblick auf Strenge und Qualität der resultierenden unteren Schranken. Dabei betrachten wir sowohl allgemeine MINLPs als auch spezifische Probleme, die sich aus der Anwendung ergeben.

Wir entwickeln ein Schnittebenenverfahren für die konvexe Hülle der zulässigen Menge von relativ allgemeinen MINLPs. Es basiert auf der simultanen Betrachtung von Nebenbedingungen und auf einem konvexen Optimierungsproblem. Dieses Separationsproblem ist nicht-differenzierbar und benötigt die konvexe Einhüllende von Linearkombinationen der Nebenbedingungen. Wir analysieren seine Struktur und Glätte ausführlich und diskutieren passende Lösungsansätze. Außerdem entwickeln wir Approximationen der konvexen Einhüllenden und ein ensprechendes approximatives Separationsproblem. Dieses führt zu schwächeren Resultaten aber zu einer höheren Anwendbarkeit.

Das obige Schnittebenenverfahren wird außerdem auf eine Menge von Nebenbedingungen angewendet, die aus bivariaten quadratischen Absolutwertfunktionen besteht. Wir präsentieren allgemeine analytische Hilfsmittel und Konzepte und bestimmen die konvexe Einhüllende für diese Funktionen unter gewissen Voraussetzungen. Diese Klasse von Funktionen wird auch bei der Modellierung von Gasnetzwerken verwendet, was es uns erlaubt den Einfluss des Schnittebenenverfahrens auf Probleme aus der Anwendung zu untersuchen.

Schließlich betrachten wir noch ein Beispiel eines optimalen Designproblems aus dem Bereich des Chemieingenieurwesens. Für das Modell einer Destillationskolonne bieten wir eine Reformulierung an und beweisen monotones Verhalten von bestimmten Folgen relevanter Variablen. Reformulierung und Monotonie werden benutzt um die Formulierung der zugehörigen zulässigen Menge zu verbessern. Insbesondere entwickeln wir eine problemspezifische Bound-Tightening-Strategie. Unsere Ergebnisse werden an einigen Testinstanzen computergestützt evaluiert.

Solution strategies for Mixed-Integer Nonlinear Programs (MINLPs) often rely on a convex relaxation of the feasible set. This relaxation is used to derive lower bounds and to evaluate the quality of local solutions. In this thesis, we discuss different approaches of constructing and improving suitable relaxations. We further analyze these relaxations with respect to tightness and quality of the resulting lower bounds. This is done for general MINLPs as well as for specific problems arising from certain real world applications.

We develop a cutting plane method for the convex hull of the feasible set of relatively general MINLPs. It is based on simultaneous considerations of the involved constraints and on solving a convex optimization problem. This underlying separation problem is non-differentiable and requires the convex envelope of linear combinations of the constraint functions. We analyze its structure and smoothness in detail, and discuss suitable solution approaches. Furthermore, we introduce approximation strategies for the convex envelope and discuss the resulting approximate version of the separation problem. This approximate version leads to weaker results but to a greater applicability.

The proposed cutting plane approach is further applied to constraint sets consisting of bivariate quadratic absolute value functions. We present general analytic tools and concepts, and derive the convex envelope of the considered functions under certain assumptions. This type of functions also emerges from the modeling of gas networks, which allows us to computationally evaluate the impact of our cutting plane approach on a real world application.

Finally, we consider an example of optimal design problems in chemical engineering. For a distillation column model, we introduce a suitable reformulation and prove monotonic behavior of several sequences of relevant variables. Reformulation and monotonicity are used to improve the formulation of the respective feasible set. In particular, we develop a problem specific bound tightening strategy. Our results are computationally evaluated on multiple test instances.