Multivalued Decision Diagrams in Optimization

研究的目的是开发多值决策图（MDDs）作为一种新的离散优化工具。 MDD，特别是二元决策图，是众所周知的电路验证和产品配置技术。 他们也提出了一个有吸引力的方法来优化，因为他们结合了联合收割机的数学规划和约束规划的优势。 数学规划在很大程度上依赖于问题的线性和其他连续松弛。 MDD同样提供容易求解的弛豫，但是弛豫是离散的并且不需要线性或不等式形式。 它们也可以在类似于切割平面生成的过程中得到加强。 与约束编程中的约束存储一样，MDD允许域过滤来减少解决方案空间，但过滤更有效，因为它操作更丰富的数据结构。 因此，本研究旨在开发基于MDD的松弛和过滤技术。这项工作是一个更大的研究计划，试图统一优化方法的一部分。 最终的目标是开发一个通用的求解器，无缝地结合了数学和约束编程技术，也许是全局优化和局部搜索，通过查看它们作为一个总体解决方案方法的特殊情况。 统一将把优化技术带到一个屋檐下，使其对用户更具吸引力，用户将不再被迫从一个求解器移动到另一个求解器来尝试不同的方法。 更重要的是，最近的研究表明，统一可以通过利用各种方法的互补优势，在解决速度上产生数量级的加速。 由于MDD将数学和约束编程的关键概念结合在一起，它们自然适合这个研究计划，并可能成为下一代求解器的一个组成部分。

The objective of the research is to develop multivalued decision diagrams (MDDs) as a novel tool for discrete optimization. MDDs, and binary decision diagrams in particular, are well known as a technique for circuit verification and product configuration. They also present an attractive approach to optimization, because they combine strengths of mathematical programming and constraint programming. Mathematical programming relies heavily on linear and other continuous relaxations of the problem. MDDs likewise provide easily solved relaxations, but the relaxations are discrete and do not require linearity or inequality form. They can also be strengthened in a process analogous to cutting plane generation. Like the constraint store in constraint programming, MDDs allow domain filtering to reduce the solution space, but the filtering is more effective because it operates on a richer data structure. The research therefore aims to develop MDD-based relaxation and filtering techniques.This work is part of a larger research program that attempts to unify optimization methods. The eventual goal is to develop a general-purpose solver that seamlessly combines techniques from mathematical and constraint programming, and perhaps global optimization and local search, by viewing them as special cases of an overarching solution methodology. Unification would bring optimization technology under one roof and make it more attractive to users, who would no longer be obliged to move from one solver to another to try different approaches. More importantly, recent research suggests that unification can yield orders-of-magnitude speedups in solution speed by exploiting complementary strengths of the various methods. Because MDDs knit together key concepts from mathematical and constraint programming, they fit naturally into this research program and could become a component of the next generation of solvers.