Decision Diagrams for Discrete optimization
Willem-Jan van Hoeve, Carnegie Mellon University
The talk provides an introduction to the use of decision diagrams for solving discrete optimization problems. A decision diagram is a graphical representation of the solution space, representing decisions sequentially as paths from a root node to a target node. By merging isomorphic subgraphs (or equivalent subproblems), decision diagrams can compactly represent an exponential solution space. This ability can reduce solving time and memory requirements potentially by orders of magnitude. That said, exact decision diagrams can still be of exponential size for a given problem, which limits their practical applicability to relatively small instances. However, recent research has introduced a scalable approach by compiling polynomial-sized relaxed and restricted diagrams that yield dual and primal bounds, respectively. These can be combined in an exact search to produce a generic decision diagram-based branch-and-bound method. We will demonstrate experimentally that this approach can be competitive with, or outperform, other exact generic solvers on a variety of problem domains.
(back)