This tutorial 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. This chapter describes how this approach provides a scalable solution method for state-based dynamic programming models. In addition, the chapter shows how this approach can be applied to, and embedded in, other computational paradigms including constraint programming, integer programming, and column elimination. After this chapter, readers will have an understanding of the basic principles of decision diagram-based optimization, an appreciation of how it compares it to other optimization methods, and an understanding of what types of optimization problems are most suitable for this new technology.
Citation
INFORMS TutORials in Operations Research, 2024