Variable ordering for decision diagrams: A portfolio approach
Variable ordering for decision diagrams: A portfolio approach
复制标题
决策图的变量排序：组合方法
DOI：
10.1007/s10601-021-09325-6
复制
发表时间：
2022
期刊：
影响因子：
1.6
通讯作者：
Willem-Jan van Hoeve
中科院分区：
文献类型：
--
作者：
Anthony Karahalios;Willem-Jan van Hoeve
松弛决策图已成功应用于解决组合优化问题，但众所周知，它们的性能强烈依赖于变量排序。我们提出了一种组合方法来从一组替代方案中选择最佳排序。我们考虑几种不同的投资组合机制：静态统一分时投资组合、使用分类器的单个最佳算法的离线预测模型、低知识算法选择和动态在线时间分配器。作为案例研究，我们比较和对比它们在图形着色问题上的表现。我们发现，在这个问题域上，动态在线时间分配器提供了最佳的整体性能。
Relaxed decision diagrams have been successfully applied to solve combinatorial optimization problems, but their performance is known to strongly depend on the variable ordering. We propose a portfolio approach to selecting the best ordering among a set of alternatives. We consider several different portfolio mechanisms: a static uniform time-sharing portfolio, an offline predictive model of the single best algorithm using classifiers, a low-knowledge algorithm selection, and a dynamic online time allocator. As a case study, we compare and contrast their performance on the graph coloring problem. We find that on this problem domain, the dynamic online time allocator provides the best overall performance.
低知识算法选择的简单规则
影响因子：
6.3
作者：
J. Christopher Beck;Eugene C. Freuder
通讯作者：
Eugene C. Freuder
影响因子：
6.3
作者：
W. V. Hoeve
通讯作者：
W. V. Hoeve