Optimization Bounds from Binary Decision Diagrams
David Bergman, Andre A. Cire, Willem-Jan van Hoeve, J. N. Hooker
INFORMS Journal on Computing · 2014 · Volume 26 · Issue 2
Abstract
We explore the idea of obtaining bounds on the 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 a 0-1 optimization problem, and how to obtain a bound for a 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 for most problem instances, it delivers tighter bounds in less computation time, than state-of-the-art integer programming software obtains by solving a continuous relaxation augmented with cutting planes.
Keywords
binary decision diagrams, independent set, relaxations
Enable JavaScript for citation tools and additional paper interactions.