15h30 - 16h30
Decision Diagrams for Discrete Optimization
This tutorial provides an overview of the recent successful
application of multivalued decision diagrams (MDDs) to represent and
solve discrete optimization problems.
The first part of the tutorial introduces limited-size MDDs to
obtain upper and lower bounds for integer optimization problems. The
resulting discrete bounds can be much stronger than continuous bounds
based on linear programming, while being faster to compute. We
present computational results on classical optimization problems
including maximum independent set, maximum cut, and set covering
In the second part we discuss the use of MDDs in the context of
constraint-based scheduling. In particular, we show how MDDs can be
effectively applied to solve complex disjunctive scheduling problems.
The resulting technology can outperform state-of-the-art industrial CP
solvers by orders of magnitude in certain cases.