Strukturelle Parameter von ILP und MILP -Instanzen aus der Praxis

Abstract

Obwohl die ganzzahlige lineare Programmierung (ILP) und die gemischte ganzzahlige Programmierung (MILP) NP-vollständige Probleme sind, schaffen es moderne Solver diese Probleme mit Millionen von Variablen oder Ungleichungen zu lösen. Trotzdem bleiben bestimmte ILP-Instanzen mit einer relativ geringen Größe immer noch ungelöst. Neueste Fortschritte haben gezeigt, dass manchmal die Struktur von graphischen Modellen der ILP- und MILP-Instanzen (gemessen durch etablierte strukturelle Parameter wie die Treewidth oder Tree-depth) ausgenutzt werden kann um diese effizient zu lösen. In dieser Arbeit analysieren wir die Struktur von graphischen Repräsentationen von ILP- und MILP-Instanzen aus der Praxis, indem wir die Werte von verschiedenen strukturellen Parametern berechnen. Unser Framework MILP-Struct stellt die Beziehungen zwischen den Variablen und Ungleichungen mittels dem Primal-, Incidence- und Dual-Graphen der ILP- oder MILP-Instanz dar. Auf diesen graphischen Modellen werden dann Unter- und Obergrenzen von den strukturellen Parametern Treewidth, Tree-depth und Torso-width berechnet, für welche in letzter Zeit Fest-Parameter-Algorithmen zum Lösen von ILP oder MILP etabliert worden sind. Die Ergebnisse von MILP-Struct angewendet auf die MIPLIB Bibliothek von praktischen ILP- und MILP-Instanzen zeigen, dass manche der berechneten Parameter tatsächlich viel kleiner als die Anzahl der Variablen sind.

Even though Integer Linear Programming (ILP) and Mixed Integer Linear Programming (MILP) are NP-complete problems, state-of-the-art solvers are able to solve instances with millions of variables or constraints. However, certain ILP instances with a relatively small size remain unsolved. Recent advances have shown that in some cases the structure of graphical models of ILP and MILP instances (measured in terms of well-established structural parameters such as treewidth and tree-depth) can be exploited to solve these problems efficiently. In this thesis, we analyze the structure of graphical representations of practical ILP and MILP instances by computing the value of these structural parameters. We present our framework MILP-Struct that captures the variable-constraint interactions by means of the primal, incidence and dual graph representation of the ILP or MILP instance. On these graphical models, MILP-Struct computes bounds for the structural parameters treewidth, tree-depth and torso-width, which have recently been shown to give rise to fixed-parameter algorithms solving ILP or MILP. Results obtained by applying MILP-Struct on the MIPLIB library of practical MILP and ILP instances show that some of the computed parameters are much smaller than the number of variables.