Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25978
Titel: Binary decision diagrams and integer programming
Verfasser: Behle, Markus
Sprache: Englisch
Erscheinungsjahr: 2007
SWD-Schlagwörter: Programmierung
Binäres Entscheidungsdiagramm
Freie Schlagwörter: BDDs
binary decision diagrams
programming
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: In this work we show how Binary Decision Diagrams can be used as a powerful tool for 0/1 Integer Programming and related polyhedral problems. We develop an output-sensitive algorithm for building a threshold BDD, which represents the feasible 0/1 solutions of a linear constraint, and give a parallel and-operation for threshold BDDs to build the BDD for a 0/1 IP. In addition we construct a 0/1 IP for finding the optimal variable order and computing the variable ordering spectrum of a threshold BDD. For the investigation of the polyhedral structure of a 0/1 IP we show how BDDs can be applied to count or enumerate all 0/1 vertices of the corresponding 0/1 polytope, enumerate its facets, and find an optimal solution or count or enumerate all optimal solutions to a linear objective function. Furthermore we developed the freely available tool azove which outperforms existing codes for the enumeration of 0/1 points. Branch & Cut is today's state-of-the-art method to solve 0/1 IPs. We present a novel approach to generate valid inequalities for 0/1 IPs which is based on BDDs. We implemented our BDD based separation routine in a B&C framework. Our computational results show that our approach is well suited to solve small but hard 0/1 IPs.
In dieser Arbeit zeigen wir, wie Binary Decision Diagrams (BDDs) als ein mächtiges Werkzeug für die 0/1 Ganzzahlige Programmierung (0/1 IP) und zugehörige polyedrische Probleme eingesetzt werden können. Wir entwickeln einen output-sensitiven Algorithmus zum Bauen eines Threshold BDDs, der die zulässigen 0/1 Lösungen einer linearen Ungleichung darstellt, und beschreiben eine parallele und-Operation für Threshold BDDs, um den BDD für ein 0/1 IP zu bauen. Des Weiteren konstruieren wir ein 0/1 IP zum Finden der optimalen Variablenordnung und zum Berechnen des Variablenordnung Spektrums eines Threshold BDDs. Zur Untersuchung der polyedrischen Struktur eines 0/1 IPs zeigen wir, wie man mit Hilfe von BDDs alle 0/1 Ecken des dazugehörigen 0/1 Polytops zählt oder enumeriert, seine Facetten enumeriert und zu einer linearen Zielfunktion eine optimale Lösung findet oder alle optimalen Lösungen zählt oder enumeriert. Darüber hinaus haben wir das frei erhältliche Tool azove entwickelt, welches bestehende Codes für die Enumerierung von 0/1 Punkten geschwindigkeitsmäßig übertrifft. Branch & Cut ist heutzutage die Methode der Wahl zum Lösen von 0/1 IPs. Wir beschreiben einen neuartigen Ansatz zur Generierung zulässiger Ungleichungen für 0/1 IPs, der auf BDDs basiert. Unsere BDD-basierte Separierungsroutine haben wir in einem B&C Framework implementiert. Unsere Rechenresultate zeigen, dass unser Ansatz gut zum Lösen kleiner und zugleich schwieriger 0/1 IPs geeignet ist.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-32007
hdl:20.500.11880/26034
http://dx.doi.org/10.22028/D291-25978
Erstgutachter: Eisenbrand, Friedrich
Tag der mündlichen Prüfung: 22-Dez-2007
SciDok-Publikation: 7-Jul-2010
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Dissertation_2208_Behl_Mark_2007.pdf897,27 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.