COmPwise: Computing Optimal Piecewise Linear Functions and Their Applications

Abstract

Piecewise linear (PWL) functions consist out of affine segments which intersect at breakpoints. They are used to fit a set of discrete data points or to approximate non-linear functions. PWL functions can be modeled by mixed-integer linear programming (MILP) techniques, where binary variables are used to assign segments. When solving large scale mixed-integer non-linear programming (MINLP) problems, PWL functions can be used to approximate the non-linearities, leading to a MILP model; this can significantly enhance computational tractability. The goals of this project are to (1) advance the state-of-the-art in models for PWL function fitting and applications thereof, (2) develop tailored solution algorithms and (3) present a non-convex nested Benders decomposition algorithm for MINLP problems based on PWL approximations. Regarding the first goal, a comparison of two existing MILP model is performed, showcasing the superiority of one model from a theoretical and experimental perspective across a number of different benchmarks. A framework for a class of problems using PWL functions, including regression and clustering as well as feature selection is proposed. This framework is extended to support vector machines. Finally, a model from the literature on PWL computations is investigated and three enhancements are proposed. Regarding the second goal, a tailored combinatorial Benders decomposition for PWL function computation with inbuilt outlier detection is presented which showcases speedups of significant magnitude. Further, an efficient method for approximating non-linear continuous functions using PWL functions, showcasing speedups of up to 100,000 times compared to the state-of-the-art, is developed. To our knowledge, this is currently the fastest approach for univariate PWL function fitting; a number of benchmark problems have been solved for the first time. An R-package has been released. Finally, a spatial branch-and-bound algorithm is developed to efficiently solve optimization problems containing univariate PWL functions. Regarding the third goal, a multi-layered decomposition framework, the so-called non-convex nested Benders decomposition, allowing to solve multi-stage (stochastic) MINLP problems with proven exactness is proposed. It uses PWL functions to approximate the MINLP by an MILP, and this approximation is dynamically refined if required. To solve the MILP, it is decomposed and certain Lagrangian dual problems are solved to iteratively generate non-convex approximations of the arising value functions. As this is computationally challenging, some alternative strategies for this step, which are either more efficient or yield cuts with favorable properties (e.g. Pareto-optimality) are explored. To broaden the theoretical understanding of the concepts used in this new framework, among them Lipschitz regularization and cut generation, their mathematical properties and interdependencies are analyzed and deep connections are revealed. Stückweise lineare (PWL) Funktionen bestehen aus affinen Segmenten, die sich an Knickpunkten schneiden. Sie dienen dazu, diskrete Datenpunkte zu approximieren oder nichtlineare Funktionen näherungsweise darzustellen. PWL-Funktionen lassen sich mit gemischt-ganzzahliger linearer Programmierung (MILP) modellieren, wobei binäre Variablen zur Segmentzuordnung verwendet werden. Bei großskaligen gemischt-ganz-zahligen nichtlinearen Optimierungsproblemen (MINLP) können PWL-Funktionen Nichtlineari-täten approximieren, wodurch ein MILP-Modell entsteht – das verbessert die Rechenbarkeit erheblich. Ziele des Projekts sind (1) die Weiterentwicklung des Stands der Technik für die Modellierung und Anwendung von PWL-Funktionen, (2) die Entwicklung passender Lösungsverfah-ren sowie (3) die Vorstellung eines nicht-konvexen geschachtelten Benders-Dekompositions-verfah-rens für MINLP-Probleme auf Basis von PWL-Approximationen. Zum ersten Ziel: Zwei bestehende MILP-Modelle zur PWL-Approximation werden verglichen, wobei sich ein Modell theoretisch und praktisch über diverse Benchmarks hinweg als überlegen zeigt. Es wird ein allgemeiner Rahmen für Probleme unter Einsatz von PWL-Funktionen – darunter Regression, Clustering und Merkmalsauswahl – vorgeschlagen und auf Support Vector Machines ausgeweitet. Zudem wird ein Modell aus der Literatur analysiert und um drei Verbesserungen ergänzt. Zum zweiten Ziel: Eine kombinatorische Benders-Dekomposition mit integrierter Ausreißererkennung zur PWL-Berechnung wird vorgestellt und zeigt deutliche Geschwindigkeitsvorteile. Außerdem wird eine effiziente Methode zur Approximation nichtlinearer Funktionen mittels PWL entwickelt, die Beschleunigungen um bis zu 100.000-fach gegenüber dem Stand der Technik erreicht. Soweit bekannt, ist dies aktuell der schnellste Ansatz zur univariaten PWL-Approximation; mehrere Benchmark-Probleme wurden erstmals gelöst. Ein entsprechendes R-Package wurde veröffentlicht. Zusätzlich wird ein spatial Branch-and-Bound-Algorithmus entwickelt, um Optimierungsprobleme mit univariaten PWL-Funktionen effizient zu lösen. Zum dritten Ziel: Ein mehrstufiges Verfahren, die sogenannte nicht-konvexe geschachtelte Benders-Dekomposition, wird eingeführt, mit dem mehrstufige (stochastische) MINLP-Proble-me exakt lösbar sind. Dabei werden PWL-Funktionen genutzt, um das MINLP als MILP zu approximieren, wobei diese Darstellung bei Bedarf dynamisch verfeinert wird. Die entstehenden MILPs werden zerlegt und bestimmte Lagrange-Dualprobleme gelöst, um nicht-konvexe Näherungen der Wertfunktionen zu erzeugen. Da dieser Schritt rechnerisch anspruchsvoll ist, werden alternative Strategien geprüft, die effizienter sind oder Schnitte mit günstigeren Eigenschaften (z.B. Pareto-Optimalität) liefern. Zur Vertiefung des theoretischen Verständnisses werden die mathematischen Eigenschaften und Zusammenhänge der genutzten Konzepte – wie Lipschitz-Regularisierung und Schnittgenerierung – untersucht und tiefere Verbindungen offengelegt.