A Local Search Framework for Compiling Relaxed Decision Diagrams
A Local Search Framework for Compiling Relaxed Decision Diagrams
复制标题
用于编译宽松决策图的本地搜索框架
DOI：
10.1007/978-3-319-93031-2_36
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Rousseau LM.
中科院分区：
文献类型：
--
作者：
Römer M;Cire A.A;Rousseau LM.
提出了一种局部搜索框架，用于构造和改进松弛决策图。该框架由一组基本的DD操作操作组成，包括本文介绍的重定向操作和通用算法方案。我们展示了该框架可用于重现几个标准的DD编译方案，并创建新的编译和改进策略。在0-1背包问题、多维背包问题和集合覆盖问题的计算实验中，比较了不同的编译方法。事实证明，对于有限宽度的dd，基于局部搜索框架的新策略总是产生更好的边界，在许多情况下，比以前发布的启发式策略产生的边界要好得多。
This paper presents a local search framework for constructing and improving relaxed decision diagrams (DDs). The framework consists of a set of elementary DD manipulation operations including a redirect operation introduced in this paper and a general algorithmic scheme. We show that the framework can be used to reproduce several standard DD compilation schemes and to create new compilation and improvement strategies. In computational experiments for the 0–1 knapsack problem, the multidimensional knapsack problem and the set covering problem we compare different compilation methods. It turns out that a new strategy based on the local search framework consistently yields better bounds, in many cases far better bounds, for limited-width DDs than previously published heuristic strategies.
登录
查看更多内容
约束规划中 AI 和 OR 技术的集成
DOI：
--
发表时间：
2016
期刊：
Lecture Notes in Computer Science
影响因子：
--
作者：
Domenico Salvagnin;M. Lombardi
通讯作者：
M. Lombardi
DOI：
--
发表时间：
2007
期刊：
International Conference on Principles and Practice of Constraint Programming
影响因子：
--
作者：
H. Andersen;T. Hadzic;J. Hooker;Peter Tiedemann
通讯作者：
Peter Tiedemann
基于决策图的优化的理论见解和算法工具
影响因子：
1.6
作者：
David Bergman;A. Ciré
通讯作者：
A. Ciré
DOI：
--
发表时间：
2008
期刊：
International Conference on Principles and Practice of Constraint Programming
影响因子：
--
作者：
T. Hadzic;J. Hooker;B. O’Sullivan;Peter Tiedemann
通讯作者：
Peter Tiedemann
寻找最佳的 BDD 放松
DOI：
--
发表时间：
2017
期刊：
Integration of AI and OR Techniques in Constraint Programming
影响因子：
--
作者：
David Bergman;A. Ciré
通讯作者：
A. Ciré