论文标题
基于决策图的分支机构与缓存以进行优势和次级优势检测
Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection
论文作者
论文摘要
基于Bergman等人引入的决策图的分支结合算法。在2016年是一个框架，用于通过动态编程公式解决离散优化问题。它通过编译一系列有界宽度的决策图来起作用，这些图可以为任何给定的子问题提供下限和上限。最终，搜索空间的每个部分都将被算法探索或修剪，从而证明了最佳性。本文通过利用动态编程模型的结构来提出新的成分，以加快搜索的速度。关键思想是通过查询在整个搜索过程中缓存的扩展阈值来防止与相同动态编程状态相对应的节点的重复扩展。这些阈值基于先前发现的部分解和Gillard等人引入的过滤技术的修剪不平等之间的优势关系。在2021年。计算实验表明，该缓存机制带来的修剪可以显着减少算法扩大的节点数量。这会导致更多的基准实例在使用较窄的决策图的同时，在更少的时间内解决了困难的优化问题。
The branch-and-bound algorithm based on decision diagrams introduced by Bergman et al. in 2016 is a framework for solving discrete optimization problems with a dynamic programming formulation. It works by compiling a series of bounded-width decision diagrams that can provide lower and upper bounds for any given subproblem. Eventually, every part of the search space will be either explored or pruned by the algorithm, thus proving optimality. This paper presents new ingredients to speed up the search by exploiting the structure of dynamic programming models. The key idea is to prevent the repeated expansion of nodes corresponding to the same dynamic programming states by querying expansion thresholds cached throughout the search. These thresholds are based on dominance relations between partial solutions previously found and on the pruning inequalities of the filtering techniques introduced by Gillard et al. in 2021. Computational experiments show that the pruning brought by this caching mechanism allows significantly reducing the number of nodes expanded by the algorithm. This results in more benchmark instances of difficult optimization problems being solved in less time while using narrower decision diagrams.
