论文标题
剥离和束缚：通过多价决策图产生更强的放松边界
Peel-and-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams
论文作者
论文摘要
决策图是用于离散优化的最先进求解器的越来越重要的工具。但是，决策图的领域相对较新，并且仍在整合传统求解器数十年来构建的技术库。我们从传统求解器中使用的温暖启动技术中汲取了灵感，以解决基于决策图的方法面临的主要挑战之一。决策图变得更加有用，因为它们被允许，但产生的成本也更高，尤其是在大量变量的情况下。我们提出了一种剥离先前构造的图的子图的方法，并将其用作最初的图表，以进行随后的迭代，我们称之为果皮和结合。我们在序列排序问题上测试了该方法，结果表明，与使用相同的传播器相比，我们的剥离和结合方案比分支和结合的方案产生更强的界限，并且计算成本大大降低。
Decision diagrams are an increasingly important tool in cutting-edge solvers for discrete optimization. However, the field of decision diagrams is relatively new, and is still incorporating the library of techniques that conventional solvers have had decades to build. We drew inspiration from the warm-start technique used in conventional solvers to address one of the major challenges faced by decision diagram based methods. Decision diagrams become more useful the wider they are allowed to be, but also become more costly to generate, especially with large numbers of variables. We present a method of peeling off a sub-graph of previously constructed diagrams and using it as the initial diagram for subsequent iterations that we call peel-and-bound. We test the method on the sequence ordering problem, and our results indicate that our peel-and-bound scheme generates stronger bounds than a branch-and-bound scheme using the same propagators, and at significantly less computational cost.
