Optimization Bounds from Binary Decision Diagrams
研究如何从基于二元决策图的离散松弛中获得优化问题的界，通过求解图中的最短或最长路径得到可分目标函数的界，并在最大独立集问题上验证了该方法比整数规划软件更快且界更紧。
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.