| Popis: |
The clique problem is one of the most well-known combinatorial optimization problems. It finds application in various contexts, such as identifying densely connected subgroups in a social network, choosing mutually compatible scheduling options, or predicting interactions in protein networks. In fact, it is universal enough even to be included as an integral part in modern mixed-integer programming (MIP) solvers, for example, in Gurobi and SCIP. In this thesis, we aim to analyse the clique problem in the role of a key component of larger models and optimization schemes. We investigate a series of use cases, ranging from general-purpose methods for MIP presolve to tailor-made approaches to energy-efficient train timetabling under uncertainty for the Nuremberg underground system. In the first part, we state five two-row and two-column MIP presolve methods, one of which we extend to employ SCIP’s clique table, allowing it to find more and stronger reductions. To efficiently apply the presolve methods we devise two hashing-based pairing mechanisms. Our computational experiments confirm the effectiveness of the overall approach and show that the impact of the extended method is twice as large as in its original version. In the second part, we deal with three special cases of the so-called clique problem with multiple-choice constraints (CPMC). For the case of staircase compatibility, strong reformulations are known, but require explicit knowledge of additional problem structure. Hence, we study the NP-complete problem to recognize this structure and show that it is solvable in polynomial time for bipartite graphs and certain m-partite graphs. In our computational experiments, we benchmark our recognition algorithms and demonstrate their benefit when embedded in a larger optimization scheme to solve a train timetabling problem. The other two special cases require the so-called dependency graph to be cycle-free or series-parallel, respectively. In each case, we state a polynomial-time dynamic programming algorithm and study polyhedral and graph-theoretic aspects. For cycle-free dependency graphs, we give a complete description of the CPMC polytope, which we apply to a train timetabling problem on real-world underground instances. For series-parallel dependency graphs, we derive the odd-clique-cycle (OCC) inequalities—generalizing the well-known odd-cycle inequalities—and present a separation algorithm for embedded OCC inequalities. In the final part, we study energy-efficient train timetabling under uncertainty. We introduce a stochastic optimization MIP model and apply a Benders decomposition approach. To find satisfying solutions, we replace each Benders subproblem with an efficiently computable sparse cut, resulting in a heuristic solution approach. In our computational experiments on real-world instances, we can reduce the total energy consumption by up to 8.8 % compared to the original timetable. Additionally, two delay recovery strategies are evaluated. All in all, we show that the clique problem is not only interesting in itself, but also serves as a powerful tool in solving more complex theoretical and real-world problems. Das Cliquenproblem ist eines der bekanntesten kombinatorischen Optimierungsprobleme. Es bildet eine Modellkomponente in vielen realen Anwendungen, wie z.B. der Identifikation eng vernetzter Teilgruppen in sozialen Netzwerken, dem Finden von Mengen paarweise kompatibler Optionen im Scheduling oder auch der Vorhersage von Interaktionen in Proteinnetzwerken. Darüber hinaus ist es in seiner Anwendbarkeit sogar so universell, dass es als integraler Bestandteil moderner Lösungssoftware für gemischt-ganzzahlige Programme, wie z.B. Gurobi oder SCIP, eingesetzt wird. Ziel dieser Dissertation ist eine Analyse des Cliquenproblems als Komponente in umfassenderen Modellen und Methoden. Dazu betrachten wir eine Reihe von Anwendungsmöglichkeiten des Cliqueproblems: Angefangen bei allgemeinen Methoden des Presolve für gemischt-ganzzahlige Programme bis hin zu hochspezialisierten Methoden für die Erstellung energieeffizienter Fahrpläne unter Unsicherheit. Wir beginnen mit fünf zwei-Zeilen und zwei-Spalten Presolve-Methoden. Für eine dieser Methoden wird eine Erweiterung entwickelt, welche sich die in SCIP vorhandene Cliquentabelle zunutze macht, um sowohl mehr als auch stärkere Reduktionen zu finden. Diese Methoden werden um zwei hashbasierte Paarfindungsmechanismen ergänzt, um die Methoden nicht auf alle Paare von Nebenbedingungen oder Variablen anzuwenden, sondern gezielt ‘günstige’ Paare zu identifizieren. Unsere Rechenexperimente bestätigen die Effektivität des Gesamtansatzes die fünf Methoden mit den beiden Paarfindungsmechanismen zu koppeln. Außerdem führt die erweiterte Presolve-Methode zu einer Verdoppelung des positiven Effektes der ursprünglichen Variante. Anschließend betrachten wir drei Spezialfälle des Cliqueproblems mit Multiple-Choice-Bedingungen (CPMC). Für den Fall der sogenannten staircase compatibility sind starke Problemreformulierungen bekannt, welche allerdings Wissen über zusätzliche Problemstruktur voraussetzt. Im Rahmen dieser Arbeit befassen wir uns daher mit der Erkennung dieser zusätzlichen Struktur. Das Erkennungsproblem ist im allgemeinen Fall NP-vollständig, kann jedoch auf bipartite Graphen sowie auf bestimmten m-partiten Graphen in Polynomialzeit gelöst werden. Auch hier können wir durch Rechenexperimente die Effektivität unserer Ergebnisse belegen: Die resultierenden Algorithmen sind nicht nur eigenständig für die Erkennung anwendbar, sondern darüber hinaus effektiv in einem umfangreicheren dreistufigen Lösungsansatz für reale Bahn-Fahrplanprobleme einsetzbar. Zwei weitere Spezialfälle des CPMC erfordern, dass der sogenannte Abhängigkeitsgraph im einen Fall kreisfrei und im anderen Fall seriell-parallel ist. In beiden Fällen geben wir einen auf dynamischer Programmierung basierenden polynomiellen Algorithmus an. Weiterhin betrachten wir sowohl polyedrische als auch graphentheoretische Aspekte dieser Spezialfälle des CPMC. Im Fall kreisfreier Abhängigkeitsgraphen bestimmen wir eine vollständige Beschreibung des CPMC-Polytops. Diese wenden wir anschließend an, um ein reales U-Bahn-Fahrplanproblem effizient zu lösen. Im Fall seriell-paralleler Abhängigkeitsgraphen leiten wir die Klasse der Ungerade-Cliquekreis-Ungleichungen her, welche eine Generalisierung der bekannten Ungerade-Kreis-Ungleichungen sind. Darüber hinaus entwickeln wir einen Separierungsalgorithmus für eingebettete Ungerade-Cliquekreis-Ungleichungen. Im letzten Teil der Arbeit befassen wir uns mit der energieeffizienten Bahn-Fahrplanung unter Unsicherheit. Wir entwickeln für dieses Anwendungsproblem zunächst ein MIP Modell basierend auf stochastischer Optimierung und beweisen, dass es durch ein Benders-Dekompositionsverfahren lösbar ist. Hierzu werden im Masterproblem zulässige Fahrpläne berechnet, während es Aufgabe des Subproblems ist, den korrekten Energieverbrauch abzubilden. Um hochqualitative Lösungen zu finden, entwickeln wir das Dekompositionsverfahren durch effizient berechenbare dünnbesetzte Schnittebenen zu einem heuristischen Verfahren weiter. Im Rahmen unserer Rechenexperimente erreichen wir mit dem heuristischen Verfahren eine Energieeinsparung von bis zu 8.8 %. Darüber hinaus evaluieren wir Kosten und Nutzen zweier Strategien zum Wiederaufholen von Verspätungen. Insgesamt zeigen wir einerseits, dass das Cliqueproblem selbst interessant ist, und anderer- seits, dass dieses auch ein leistungsfähiges Werkzeug zum Lösen komplexer theoretischer und realer Probleme sein kann. |
