Item

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 \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.