Optimization Bounds from Binary Decision Diagrams

We explore the idea of obtaining bounds on the optimal value of an optimization problem from a discrete relaxation based on binary decision diagrams (BDDs). We show how to construct a BDD that represents a relaxation of an optimization problem with binary variables, and how to obtain a bound for any separable objective function by solving a shortest (or longest) path problem in the BDD. As a test case we apply the method to the maximum independent set problem on a graph. We find that it can can deliver significantly tighter bounds, in far less computation time, than state-of-the-art integer programming software obtains for an integer programming formulation by solving a continuous relaxation augmented with cutting planes.