Multivalued Decision Diagrams in Optimization

点击翻译按钮获取中文摘要

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.