期刊
INFORMS JOURNAL ON COMPUTING
卷 28, 期 1, 页码 47-66出版社
INFORMS
DOI: 10.1287/ijoc.2015.0648
关键词
programming; integer; branch and bound; dynamic programming; deterministic; networks/graphs
资金
- National Science Foundation [NSF] [1130012]
- Air Force Office of Scientific Research [AFOSR] [FA9550-11-1-0180]
- Directorate For Engineering
- Div Of Civil, Mechanical, & Manufact Inn [1130012] Funding Source: National Science Foundation
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据