Binary decision diagrams and integer programming

Abstract

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.