Discrete Optimization with Decision Diagrams

We propose a general branch-and-bound algorithm for discrete optimization in which binary decision diagrams (BDDs) play the role of the traditional linear programming relaxation. In particular, relaxed BDD representations of the problem provide bounds and guidance for branching, and restricted BDDs...

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 2016-12, Vol.28 (1), p.47-66
Main Authors: Bergman, David, Cire, Andre A., van Hoeve, Willem-Jan, Hooker, J. N.
Format: Article
Language:English
Subjects:
Algorithms
branch and bound
deterministic
Dynamic programming
Heuristic
integer
Integer programming
Linear programming
networks/graphs
Optimization
programming
Solvers
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose a general branch-and-bound algorithm for discrete optimization in which binary decision diagrams (BDDs) play the role of the traditional linear programming relaxation. In particular, relaxed BDD representations of the problem provide bounds and guidance for branching, and restricted BDDs supply a primal heuristic. Each problem is given a dynamic programming model that allows one to exploit recursive structure, even though the problem is not solved by dynamic programming. A novel search scheme branches within relaxed BDDs rather than on values of variables. Preliminary testing shows that a rudimentary BDD-based solver is competitive with or superior to a leading commercial integer programming solver for the maximum stable set problem, the maximum cut problem on a graph, and the maximum 2-satisfiability problem. Specific to the maximum cut problem, we tested the BDD-based solver on a classical benchmark set and identified tighter relaxation bounds than have ever been found by any technique, nearly closing the entire optimality gap on four large-scale instances.
ISSN:1091-9856
1526-5528
1091-9856
DOI:10.1287/ijoc.2015.0648