Loading…
On cutting planes for mixed-integer nonlinear programming
On cutting planes for mixed-integer nonlinear programming
Serrano Musalem, Felipe
FG Software und Algorithmen für die diskrete Optimierung
Mixed-integer nonlinear programming is a powerful technology that allows us to model and solve problems involving nonlinear functions, continuous, and discrete variables. The state-of-the-art solvers of mixed-integer nonlinear programs (MINLPs) use a combination of, among other techniques, branch- and-bound and cutting planes. In the late ’90s, solvers for mixed-integer linear programs saw an increase in performance due to the incorporation of general- purpose cutting planes. In this thesis, we deepen our understanding of a classical cutting planes algorithm, develop a strengthening technique, and two new cutting planes for MINLPs. We first show that Veinott’s supporting hyperplane algorithm is a particular case of Kelley’s cutting plane algorithm. We further extend the applicability of Veinott’s supporting hyperplane algorithm to solve convex problems repre- sented by non-convex functions. We then develop a technique to strengthen cutting planes for non-convex MINLPs. Many cuts for non-convex MINLPs strongly rely on the domain of the variables: tighter bounds produce tighter cuts. Using the point to be separated, we show that we can restrict the feasible region and still ensure the validity of the resulting cutting plane. Finally, we develop two intersection cuts for non-convex MINLP. The first one is a technique to construct S-free sets for any factorable MINLP. For the second one, we show how to build maximal quadratic-free sets, from which we compute intersection cuts. These last cuts reduce the average running time of the solver SCIP by 20% on hard MINLPs.
Die gemischt-ganzzahlige nichtlineare Programmierung ist eine leistungsstarke Technik, mit der wir Probleme modellieren und lösen können, die nichtlineare Funktionen und kontinuierliche und diskrete Variablen enthalten. Die hoch- modernen Löser für gemischt-ganzzahlige nichtlineare Programme (MINLPs) verwenden unter anderem eine Kombination der Branch-and-Bound-Methode und Schnittebenengenerierung. In den späten 90er Jahren erfuhren die Löser für gemischt-ganzzahlige lineare Programme eine Leistungssteigerung durch die Einbeziehung von universell nutzbaren Schnittebenen. In dieser Arbeit vertiefen wir unser Verständnis eines klassischen Schnitt- ebenen-Algorithmus, wir entwickeln eine Verstärkungstechnik und zwei neue Schnittebenen für MINLPs. Zunächst zeigen wir, dass der Stützhyperebenen-Algorithmus von Veinott ein Sonderfall des Kelley’schen Schnittebenen-Algorithmus ist. Darüber hinaus erweitern wir die Anwendbarkeit von Veinotts Stützhyperebenen-Algorithmus auf die Lösung konvexer Probleme, die durch nicht-konvexe Funktionen reprä- sentiert werden. Anschließend entwickeln wir eine Technik zur Verstärkung der Schnittebe- nen für nicht-konvexe MINLPs. Viele Schnitte für nicht-konvexe MINLPs hängen stark vom Wertebereich der Variablen ab: Strengere Schranken erzeu- gen stärkere Schnitte. Anhand des zu separierenden Punktes zeigen wir, dass wir die zulässige Region einschränken können und dennoch die Gültigkeit der resultierenden Schnitte beibehalten. Schließlich entwickeln wir zwei Überschneidungsschnittebenen für nicht- konvexe MINLPs. Der erste Schnitt ist eine Technik zur Konstruktion S-freier Mengen für beliebige faktorisierbare MINLPs. Für den zweiten Schnitt zeigen wir, wie man maximal quadratisch-freie Mengen bildet, aus denen wir Über- schneidungsschnittebenen berechnen. Diese Schnitte reduzieren die durch- schnittliche Laufzeit des Lösers SCIP um 20% bei schwierigen Problemen.
