Theoretical insights and algorithmic tools for decision diagram-based optimization
Theoretical insights and algorithmic tools for decision diagram-based optimization
复制标题
基于决策图的优化的理论见解和算法工具
作者：
David Bergman;A. Ciré
最近，决策图的使用已经成为解决离散优化问题的一种可行的通用解决方法。决策图数据结构用于精确或近似地显式表示给定问题的一组可行解。基于决策图的技术已经成功地应用于从调度到组合优化的各种应用，并且往往优于商业最先进的约束编程和整数编程技术。然而，缺乏对近似决策图的质量的深入的理论研究，以及类似于整数规划中如何使用割平面的由近似决策图提供的收紧松弛界限的结构化技术的发展。本文对近似决策图的强度进行了分析，并对线性目标函数问题的几种紧界方法进行了描述。
The use of decision diagrams has recently emerged as a viable general solution approach for solving discrete optimization problems. The decision diagram data structure is used to explicitly represent, either exactly or approximately, the set of feasible solutions to a given problem. Techniques based on decision diagrams have been successfully used on a diverse set of applications, ranging from scheduling to combinatorial optimization, and have often outperformed commercial state-of-the-art constraint programming and integer programming technology. Lacking, however, is a thorough theoretical investigation into the quality of approximate decision diagrams, as well as the development of structured techniques for tightening relaxation bounds provided by approximate decision diagrams, analogously to how cutting-planes are used in integer programming. This paper provides an analysis of the strength of approximate decision diagrams, as well as the description of several bound-tightening procedures for problems with linear objective functions.