Binary Decision Diagrams and Integer Programming

Download or read book Binary Decision Diagrams and Integer Programming written by and published by . This book was released on with total page pages. Available in PDF, EPUB and Kindle. Book excerpt: 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 \emph{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 orderand 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 \texttt{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 Branch~\ & ~Cut framework. Our computational results show that our approach is well suited to solve small but hard 0/1~IPs.