Multivalued decision diagrams (MDDs) are layered directed acyclic graphs that can, in principle, compactly represent all solutions to a given combinatorial problem. MDDs, and binary decision diagrams in particular, are best known as a technique for circuit verification and product configuration, but they have recently also been introduced as an attractive approach to discrete optimization. In this talk, I will describe how limited-width MDDs can serve as discrete relaxations (or restrictions) for combinatorial optimization problems. Specific example applications in the context of Constraint Programming and Integer Programming will illustrate this approach.
This talk is based on joint work with David Bergman, Andre A. Cire, Sam Hoda, and John N. Hooker.