Hybrid metaheuristics based on large neighborhood search and mixed integer linear programming for the directed feedback vertex set problem

Abstract

Das Directed Feedback Vertex Set (DFVS) Problem ist ein NP-vollständiges, kombinatorisches Optimierungsproblem, das für ungewichtete, gerichtete Graphen spezifiziert ist, und dessen Ziel es ist, ein DFVS minimaler Größe zu finden. Eine Knotenmenge wird als Directed Feedback Vertex Set (gerichtete kreiskritische Knotenmenge) bezeichnet, wenn sie zumindest einen Knoten eines jeden gerichteten Kreises im Graphen enthält, sodass das Entfernen der Knotenmenge aus dem Graphen zu einem gerichteten azyklischen Graphen (engl. directed acyclic graph, DAG) führt. Das Feedback Vertex Set Problem findet in vielen verschiedenen Bereichen Anwendung, wie zum Beispiel bei der Verklemmungserkennung und -beseitigung in Betriebssystemen, bei computerunterstützten Konstruktionsanwendungen und in der chemischen Verfahrenstechnik. Das Ziel dieser Diplomarbeit ist die Entwicklung hybrider Metaheuristiken, die innerhalb eines Zeitlimits hochwertige Lösungen für das DFVS Problem erzeugen. Am Beginn unserer Lösungsansätze steht jeweils eine Prozedur zur Reduktion der Graphengröße, in der aus der Literatur bekannte Reduktionsregeln zur Anwendung kommen, und die den Suchraum für mögliche Lösungen verkleinert. Danach wird eine Greedy-Heuristik verwendet, um eine erste Lösung zu erzeugen, welche im Weiteren mit einer lokalen Suche verbessert wird. Unsere Metaheuristik besteht aus einer Large Neighborhood Search (LNS), deren Nachbarschaften jeweils von einer zerstörenden und einer reparierenden Operation bestimmt werden. Wir präsentieren zwei Nachbarschaften, in denen entweder Knoten von der momentanen Lösung zum entsprechenden DAG hinzugefügt werden (enlarge-DAG) oder umgekehrt (enlarge-(partial-)DFVS). Eine gültige Lösung wird dann wiederhergestellt, indem das resultierende kleinere Teilproblem in ein gemischt-ganzzahliges lineares Optimierungsmodell (engl. mixed integer linear program, MILP) überführt und mit entsprechender Software gelöst wird. Diese Kombination aus LNS und MILP führt zu einer Hybridisierung der Metaheuristik. Wir stellen zwei MILP Modelle für das DFVS Problem vor, welche sowohl als Bestandteil der hybriden LNS als auch in eigenständigen Lösungsverfahren verwendet werden können. Die CEC genannte Formulierung basiert auf Constraints zur Entfernung von Kreisen (engl. cycle elimination constraints). Die Formulierung namens MTZ wurde inspiriert von den Kurzzyklusungleichungen, auch Subtour-Eliminationsbedingungen genannt, nach Miller, Tucker und Zemlin und ist eine Abwandlung eines Modells aus der Literatur. Weiters präsentieren wir verschiedene Strategien zur Wahl des Zerstörungsgrades in der LNS und auch eine Vorgehensweise, wie die jeweils passende MILP Formulierung für jede Instanz gewählt werden kann. Das Hinzufügen dieser Erweiterungen ergibt mehrere Varianten unserer hybriden Metaheuristik, welche auf typischen Instanzen getestet und bezüglich ihrer durchschnittlich erreichten Lösungsqualität miteinander verglichen werden. Unsere praktische Untersuchung zeigt, dass alle Varianten der hybriden LNS höhere Durchschnittswerte für die Lösungsqualität erzielen als die eigenständigen Lösungsverfahren basierend auf den MILP Formulierungen. Außerdem übertrifft die Leistung der CEC Formulierung zusammen mit der enlarge-DAG Nachbarschaft die der anderen Ansätze, welche MTZ oder auch die Kombination von MTZ und der enlarge-partial-DFVS Nachbarschaft verwenden, wenn eine zeitliche Beschränkung festgelegt wird. Das dynamische Auswahlverfahren für den Zerstörungsgrad, das auf der Anzahl an Kreisen mit Länge zwei im Graphen beruht, erzielt die besten Ergebnisse aller untersuchten Strategien. Die durchschnittliche Lösungsqualität wird weiter verbessert, wenn dieser Ansatz mit der dynamischen Auswahl der MILP Formulierung gepaart wird. Des Weiteren ist es uns gelungen, mit den Hauptvarianten unserer hybriden Metaheuristik die Leistungen zweier state-of-the-art Lösungsverfahren aus der Literatur, welche auf Simulated Annealing basieren, zu übertreffen.

The directed feedback vertex set (DFVS) problem is an NP-complete combinatorial optimization problem defined on unweighted, directed graphs with the goal of finding a DFVS of minimum cardinality. A set of vertices is called a directed feedback vertex set if it contains at least one vertex of every directed cycle in the graph, such that the removal of the set from the graph leads to a directed acyclic graph (DAG). The general feedback vertex set problem is relevant for many different areas and real world scenarios including deadlock detection and recovery in operating systems, computer-aided design applications, and chemical engineering. The aim of this work is to develop hybrid metaheuristics that provide solutions of high quality for challenging DFVS problem instances within a given time limit. Our solving approaches start with a graph reduction procedure using reduction rules from the literature to decrease the size of the graph and reduce the search space for possible solutions. An initial solution is generated with a greedy construction heuristic and improved with a classical local search procedure. For the metaheuristic framework, we employ large neighborhood search (LNS) with neighborhoods that are each defined by a destroy and a repair method. We introduce two neighborhood structures which are based on either moving vertices from the current solution to the corresponding DAG (enlarge-DAG) or the other way around (enlarge-(partial-)DFVS). A valid solution is restored by encoding the resulting smaller subproblem with a mixed integer linear programming (MILP) formulation and solving it with an existing solver. This combination of LNS and MILP leads to the hybridization of the metaheuristic. We propose two MILP formulations for the DFVS problem, which can be used within the hybrid LNS as well as in standalone solving procedures. One formulation called CEC is based on cycle elimination constraints and the other formulation MTZ is inspired by the subtour elimination constraints from Miller, Tucker, and Zemlin and derived from the literature. We also investigate various strategies for selecting the degree of destruction for the LNS and a technique for dynamically choosing the MILP formulation for each instance. These enhancements lead to multiple variants of our hybrid metaheuristic, which are tested on benchmark instances and compared in terms of the achieved average solution quality. The results of our computational study show that all hybrid LNS variants achieve higher average solution qualities than the standalone MILP solving procedures. Furthermore, the CEC-based formulation together with the enlarge-DAG neighborhood outperforms other approaches using the MTZ-based formulation as well as the combination of MTZ and enlarge-partial-DFVS neighborhood when having a time limit. The dynamic selection strategy for the degree of destruction that is based on the number of cycles of length two in the respective graph performs the best out of all tested strategies. Enhancing this approach with the dynamic selection of the MILP formulation leads to further improvements of the solution quality. Moreover, the main variants of our hybrid metaheuristic manage to outperform two state-of-the-art solving procedures from the literature, which are based on simulated annealing.