On Finding the Optimal BDD Relaxation
On Finding the Optimal BDD Relaxation
复制标题
寻找最佳的 BDD 放松
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Ciré
中科院分区：
文献类型：
--
作者：
David Bergman;A. Ciré
本文提出了一个识别有限宽度松弛二叉决策图（BDDs）的优化模型，该模型具有最紧的松弛边界。开发的模型是一个网络设计模型，并用于确定哪些节点和弧应该在一个宽松的BDD，使目标函数界尽可能接近最优值。该模型是专门为0-1背包问题，但可以扩展到其他的问题类，已被调查的研究流中使用决策图的组合优化问题。初步的实验结果表明，由放松BDD提供的界限是远远优于上级通过以前公布的编译算法构造的放松BDD实现的界限。
This paper presents an optimization model for identifying limited-width relaxed binary decision diagrams (BDDs) with tightest possible relaxation bounds. The model developed is a network design model and is used to identify which nodes and arcs should be in a relaxed BDD so that the objective function bound is as close to the optimal value as possible. The model is presented specifically for the 0–1 knapsack problem, but can be extended to other problem classes that have been investigated in the stream of research on using decision diagrams for combinatorial optimization problems. Preliminary experimental results indicate that the bounds provided by the relaxed BDDs are far superior to the bounds achieved by relaxed BDDs constructed via previously published compilation algorithms.