1 Presentation

• 
  03:30 PM - 04:30 PM

  Decision Diagrams for Discrete Optimization

  • Willem-Jan van Hoeve, presenter, Carnegie Mellon University

  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
  problems.

  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.