Advances in decomposition approaches for mixed Integer linear programming

Abstract

In dieser Arbeit werden unterschiedliche Zerlegungsansätzen für gemischt-ganzzahlige lineare Optimierung (engl. mixed integer linear programming, MILP) untersucht. Hierzu kommen etablierte Techniken wie das Schnittebenenverfahren, Spaltengenerierung und die Logik-basierte Benders-Zerlegung, sowie neuere Verfahren basierend auf schrittweise verfeinerten Relaxationen zum Einsatz. Insbesondere werden Kombinationen dieser Algorithmen mit anderen Techniken, wie Constraintprogrammierung oder (Meta-)Heuristiken verwendet. Im Rahmen dieser Arbeit werden zwei Hauptziele verfolgt. Zum einen soll gezeigt werden, wie mit diesen Techniken komplexe Optimierungsprobleme gelöst werden. Dabei wird zum einen darauf eingegangen, wodurch sich die unterschiedlichen Verfahren für bestimmte Problemstellungen besonders eignen bzw. welche Anpassungen und Erweiterungen notwendig sind, um deren Effektivität zu steigern. Zum anderen werden die gewonnenen Erkenntnisse genutzt, um die Verfahren weiterzuentwickeln. Die gezogenen Schlussfolgerungen sowie das Potential der entwickelten Verbesserungen werden durch ausführliche Experimente demonstriert. Als erstes Verfahren kommt Spaltengenerierung in Kombination mit dem Schnittebenenverfahren zur Lösung des Netzwerkentwurfproblems mit Verstärkern zum Einsatz. Eine Nebenbedingung dieses Problems betreffend die zurückgelegten Distanzen im Netzwerk wird dabei mithilfe einer Transformation des Basisgraphen in einen sogenannten Kommunikationsgraphen modelliert. Dadurch wird eine Zerlegung ermöglicht, die im Gegensatz zu einem ähnlichen Ansatz aus der Literatur den Aufwand im Unterproblem reduziert. Als Zweites wird ein Algorithmus basierend auf Logik-basierter Benders-Zerlegung entwickelt für die Lösung einer selektiven Variante des Dial-a-Ride Problems entwickelt. Der Zerlegungsansatz ermöglicht eine Aufteilung in einen Optimierungsaspekt für die Anfragenaufteilung und einen zweiten Aspekt, der die Gültigkeit der entstehenden Routen prüft. Dadurch können spezialisierte Algorithmen angewandt werden. Der Optimierungsaspekt wird durch ein MILP-Modell, gestärkt durch Schnittebenen basierend auf Relaxationen des Subproblems, gelöst. Für das Routenplanungsproblem kommt eine Kombination aus Constraintprogrammierung und MILP zum Einsatz. Der Benders Algorithmus wird durch heuristische Techniken beschleunigt. Darüber hinaus werden unterschiedliche Strategien zur Berechnung der Benders Schnitte untersucht. Am effektivsten zeigte sich eine Variante, die Schnitte aus ungültigen Strukturen kleinster Kardinalität ableitet. Diese erscheint vielversprechend für zukünftige Arbeiten in diesem Gebiet. Der übrige Teil dieser Arbeit beschäftigt sich mit erweiterten Modellen, die mithilfe von Relaxationen gelöst werden. Als erste Anwendung wird ein Terminplanungsproblem untersucht, bei dem eine besonders feine Zeitauflösung berücksichtigt werden muss. Etablierte MILP-Modelle sind entsprechend den Erkenntnissen der bestehenden Literatur unter solchen Voraussetzung ineffektiv. Als Alternative wird eine Relaxation entwickelt, die aufeinanderfolgende Zeitpunkte in Zeitintervalle aggregiert. Auf diese Weise kann die Problemgröße deutlich reduziert werden. Allerdings kann die dadurch verlorene Genauigkeit zur Verletzung von Nebenbedingungen führen. Um Gültigkeit zu gewährleisten wird die Relaxation durch schrittweises Aufspalten der Intervalle nach und nach verfeinert. Mithilfe von (Meta-)Heuristiken werden aus den ungültigen Lösungen gültige Zwischenlösungen abgeleitet. Ein besonderer Fokus liegt auf der Entwicklung und dem Vergleich von Verfahren zum Aufspalten der Zeitintervalle. Der erfolgreichste Algorithmus nutzt Informationen, die aus den heuristisch berechneten Zwischenlösungen extrahiert werden, um Rückschlüsse auf die Ursachen der verletzten Nebenbedingungen zu ziehen. Das neue Verfahren erreicht dadurch eine deutliche Verbesserung gegenüber den etablierten MILP-Ansätzen der Literatur. Diese neue Technik erscheint auch vielversprechend für andere Probleme mit ähnlichen Eigenschaften. Mithilfe des nächsten Ansatzes wird die gerichtete Variante des obengenannten Netzwerkentwurfproblems mit Verstärkern gelöst. Um eine abgewandelte Nebenbedingung zu berücksichtigen, kommen sogenannte layered graphs anstatt des zuvor verwendeten Kommunikationsgraphen zum Einsatz. Layered graphs erweitern den Graphen des Originalproblems anhand einer oder mehrerer Problemdimensionen, um effektivere MILP-Formulierungen zu ermöglichen. Im Rahmen des betrachteten Problems fügen wir Knotenkopien in Bezug auf die zurückgelegten Distanzen im Graphen ein. Um problematische Graphengrößen infolge rationaler Distanzen zu vermeiden, kommt ein dynamisches Verfahren zum Einsatz. Dazu werden rationale Distanzen abgerundet und dadurch verletzte Nebenbedingungen mithilfe von Schnittebenen behandelt. Darüber hinaus wird das resultierende Modell durch weitere Ungleichungen zur Stärkung und Symmetrievermeidung ergänzt. Die durchgeführten Experimente zeigen, dass Nebenbedingungen infolge des Rundens nur selten verletzt werden und die Separierung in der Praxis somit sehr effektiv arbeitet. In vielen Fällen sind Modelle basierend auf layered graphs bereits bei integralen Eingaben zu groß, um effektiv genutzt werden zu können. Als Abhilfe kann ein Verfahren ähnlich des Algorithmus für das obige Terminplanungsproblem eingesetzt werden. Anstatt Zeitpunkte zu aggregieren, werden Knotenkopien weggelassen und Kanten entsprechend umgelenkt. Der entstehende Ansatz basiert auf der Erkenntnis, dass optimale Lösungen meist mit einer (kleinen) Teilmenge der Knoten bestimmt werden können. Der Erfolg des Verfahrens hängt hier stark von der Strategie ab, anhand derer iterativ weitere Knotenkopien in der Relaxation ergänzt werden, um eine optimale Lösung zu berechnen. Zu diesem Zweck werden Pfad-basierte Techniken, gestützt auf strukturelle Informationen des layered graph, entwickelt. Die Effektivität dieser neuen Verfahren wird anhand von Experimenten mit zwei unterschiedlichen Optimierungsproblemen demonstriert.

In this thesis we consider different decomposition approaches for mixed integer linear programming (MILP). We work with well-known techniques from the literature such as cutting plane methods, column generation, and logic-based Benders decomposition but also more recently developed approaches based on iteratively refined relaxations. Moreover, we consider combinations of these algorithms and integrate other techniques such as constraint programming and/or (meta-)heuristics. The aim of this thesis is twofold. First, we want to exploit these methods to solve challenging optimization problems. Thereby we investigate what makes a specific approach effective for dealing with a particular application and which adjustments and extensions are important to improve performance. Second, we use the gained insights to advance the methods. The merits of our discoveries are supported by extensive computational studies that underline the potential of the proposed enhancements. The first algorithm we consider is based on column generation in combination with cutting planes for solving the network design problem with relays. We address a distance restriction imposed by this problem through transforming the input graph to a so-called communication graph. Thereby we manage to overcome the limitations of a previous column generation model from the literature that suffers from a rather unbalanced decomposition due to shifting too much effort into the pricing subproblem. The second decomposition approach considered in this thesis is based on logic-based Benders decomposition. Experiments are conducted for a selective variant of the dial-a-ride problem. In terms of the decomposition we achieve a separation into an optimization-based request selection aspect and a feasibility-related routing part. Consequently, we can exploit specialized algorithms to solve each of them as efficiently as possible. The selection problem is tackled by a MILP approach that we strengthen through cutting planes derived from subproblem relaxations. The routing problem is solved through a hybrid of constraint programming and MILP. We enhance the Benders algorithm by heuristic speedup techniques and consider different strategies for computing Benders cuts. An approach deriving Benders cuts from infeasible substructures of minimum cardinality is proven to be highly effective and also promising for other work in this area. In the remainder of the thesis we focus on algorithms based on extended formulations that are solved through relaxations. The first application we consider is a scheduling problem. We investigate a scenario that demands a very fine-grained time discretization. Traditional MILP formulations are known to be inefficient in this context due to the large number of time instants that have to be considered. We develop an alternative based on a relaxation obtained by aggregating subsequent time instants into so-called time buckets. Scheduling in terms of this aggregation is less precise and might therefore lead to infeasibilities, however, also helps to substantially decrease the problem size. We retain feasibility and achieve optimality by iteratively splitting time buckets to improve accuracy where necessary. Moreover, we also exploit the relaxation to derive intermediate feasible solutions by (meta-)heuristics. Considerable effort is invested into developing and testing strategies for implementing the refinement step in which the buckets are subdivided. Our most successful algorithm is based on incorporating additional knowledge from the intermediate solutions to address the remaining infeasibilities as effectively as possible. In comparison to standard MILP formulations from the literature we show that our algorithm performs significantly better. Due to its generality our approach is also promising for other problems with similar characteristics. The second approach based on relaxations is used to solve the directed variant of the network design problem with relays. To consider a modified side constraint we use layered graphs instead of the aforementioned transformation to a communication graph. The idea of layered graphs is to extend a base graph along one or multiple dimensions to state enhanced MILP formulations. In terms of the investigated problem we introduce node copies according to the traversed distance within the graph. To avoid prohibitive graph sizes caused by fractional inputs we consider a dynamic approach. We obtain a relaxation through rounding down all fractional distance values and address potential infeasibilities by cutting planes. Further strengthening inequalities and symmetry breaking constraints are added to enhance the resulting model. Our experiments indicate that infeasibilities in the relaxation are rare, which makes our separation approach effective in practice. Often the size of layered graphs is prohibitive already for integral inputs. In these situations we can employ a strategy similar to the algorithm considered for high-resolution scheduling. Instead of aggregating time instants we omit node copies and redirect arcs accordingly. The resulting iterative algorithm is based on the observation that only a (small) subset of the nodes is required to obtain optimal solutions. To this end we successively reintroduce some of the omitted node copies until optimality can be proven. Similar to the scheduling problem the success of such an algorithm strongly depends on the strategy according to which the graph is extended in each iteration. We develop new path-based approaches to benefit from the structural knowledge encoded in the layered graph relaxation. A computational study on two benchmark problems shows the effectiveness of these strategies.