<div class="csl-bib-body">
<div class="csl-entry">Dittmer, V. (2018). <i>Strukturelle Parameter von ILP und MILP -Instanzen aus der Praxis</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2018.52362</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2018.52362
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/4351
-
dc.description.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.
de
dc.description.abstract
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.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Treewidth
en
dc.subject
Treedepth
en
dc.subject
Integer Linear Programming
en
dc.title
Strukturelle Parameter von ILP und MILP -Instanzen aus der Praxis
en
dc.title.alternative
Structural parameters of practical ILP and MILP instances
de
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2018.52362
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Verena Dittmer
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Ganian, Robert
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen