# Decision Diagrams for Optimization

Overview People Publications and software Presentations

### News

[2/10/2014] A preprint of the CPAIOR paper on parallel optimization with decision diagrams can be downloaded below, together with the source code.

[1/28/2014] Video's of the AAAI 2013 tutorial are now available online, see below.

[1/22/2014] The paper ``BDD-Based Heuristics for Binary Optimization'' has been accepted in the Journal of Heuristics.

[1/10/2014] The paper ``MDD Propagation for Sequence Constraints'' has been accepted in the Journal of Artificial Intelligence Research (JAIR).

[1/5/2014] Our paper on MDD relaxations for sequencing and scheduling is now formally published: http://dx.doi.org/10.1287/opre.2013.1221

[10/12/2013] The session on decision diagrams for optimization at the INFORMS Annual Meeting 2013 was very well attended. All presentations can be downloaded below.

[7/15/2013] The syllabus for the AAAI 2013 Tutorial Forum can be found here. The slides can also be downloaded, as well as the solutions to the exercises.

### Overview

In this research project we utilize decision diagrams to represent discrete
optimization problems. Decision diagrams provide a compact representation
of the solution set of a given problem, although the size may grow exponentially
large. We have therefore developed *approximate decision diagrams* that
have a fixed (polynomial) limit on their size.

As an example, consider the following set covering problem on six binary variables:

Figure 1 below depicts an exact binary decision diagram (BDD), representing all solutions to the problem. A shortest path, indicated in blue, represents an optimal solution with objective value 2. This exact BDD has `width' 4, where width stands for the maximum number of nodes in any layer. By imposing a limited maximum width we obtain a relaxed BDD. Figure 2 depicts a relaxed binary decision diagram with maximum width 3. It represents all solutions as well as non-solutions. The shortest path in the relaxed BDD is 1, which serves as a lower bound to the problem.

We have successfully applied decision diagrams in the context of

- Discrete Optimization: Limited-width decision diagrams
can be deployed as
*relaxations*to provide bounds on the objective, and as*restrictions*to provide feasible solutions. They can naturally be applied in concert to provide an exact solver similar to traditional branch and bound methods. - Constraint Programming: By propagating approximate decision diagrams instead of the traditional variable domains more information can be communicated between the constraints of the problem. This can lead to earlier detection of inconsistencies, smaller search trees, and faster solution times.
- Constraint-Based Scheduling: In addition to improved constraint propagation, decision diagrams can be used to reason more effectively on the objective in the context of scheduling. This can speed up existing state-of-the-art solvers by orders of magnitude, for example for disjunctive scheduling with sequence-dependent setup times.
- Dynamic Programming: Decision diagrams are closely related to dynamic programming, but provide a more general framework.

### People

Faculty at Carnegie Mellon University:

Current and former PhD students:

- Sam Hoda (graduated 2010)
- David Bergman (graduated 2013) (U Connecticut)
- Andre Cire
- Brian Kell
- Marla Slusky

Collaborators at other institutions:

- Henrik Reif Andersen
- Tarik Hadzic (United Technologies)
- Ashish Sabharwal (IBM)
- Horst Samulowitz (IBM)
- Vijay Saraswat (IBM)
- Barry O'Sullivan (UC Cork)
- Louis-Martin Rousseau (Ecole Polytechnique de Montreal)
- Peter Tiedemann
- Tallys Yunes (U Miami)

### Publications and Software

*The documents provided on this page are preprints. The copyright for the published documents
rests with the author(s) and the journals or conferences where they were published.
Where applicable, the source code and benchmark instances are provided. The software
can be freely used but comes with no warranty.*

D. Bergman, A. A. Cire, A. Sabharwal, H. Samulowitz, V. Saraswat, and W.-J. van Hoeve.
Parallel Combinatorial Optimization with Decision Diagrams. In *Proceedings of CPAIOR*,
Springer, 2014.

D. Bergman, A. A. Cire, W.-J. van Hoeve, and J. N. Hooker.
Discrete
Optimization with Decision Diagrams. *Under Review*, 2013.

A. A. Cire and W.-J. van Hoeve.
Multivalued Decision Diagrams for Sequencing Problems.
*Operations Research* 61(6): 1411-1428, 2013.

D. Bergman, A. A. Cire, W.-J. van Hoeve, and J. N. Hooker.
Optimization Bounds from Binary Decision Diagrams. *INFORMS Journal on Computing*,
to appear.

- Source code (C++): opt_bounds_bdd-src.tar.gz
- Benchmark instances: opt_bounds_bdd-instances.tar.gz

D. Bergman, A. A. Cire, and W.-J. van Hoeve.
MDD Propagation for Sequence Constraints. *JAIR*, accepted for publication.

D. Bergman, A. A. Cire, W.-J. van Hoeve, and T. Yunes.
BDD-Based Heuristics for Binary Optimization.
*
Journal of Heuristics*, to appear.

D. Bergman.
New Techniques for Discrete Optimization. *PhD thesis*, Carnegie Mellon University, 2013.

J. N. Hooker. Decision Diagrams and Dynamic Programming.
In *Proceedings of CPAIOR*. LNCS 7874, pp. 94-110. Springer, 2013.

B. Kell and W.-J. van Hoeve.
An MDD Approach to Multidimensional Bin Packing.
In * Proceedings of CPAIOR*, LNCS 7874, pp. 128-143. Springer, 2013.

- Benchmark instances:
6-18-6-instances.txt (6 dimensions, 18 items, 6 bins. The instances
are named 6-18-6-
`β`_`n`, where`β`is the percentage bin slack and`n`is a sequential number to distinguish instances with identical parameters.)

A. A. Cire and W.-J. van Hoeve.
MDD Propagation for Disjunctive Scheduling.
In *Proceedings of ICAPS*, pp. 11-19. AAAI Press, 2012.

D. Bergman, A.A. Cire, W.-J. van Hoeve, and J.N. Hooker.
Variable Ordering for the Application of
BDDs to the Maximum Independent Set Problem. In *Proceedings of CPAIOR*. LNCS 7298, pp. 34-49. Springer, 2012.

D. Bergman, W.-J. van Hoeve, and J. N. Hooker.
Manipulating MDD Relaxations for Combinatorial Optimization. In *Proceedings of CPAIOR*. LNCS 6697, pp. 20-35. Springer, 2011.

S. Hoda.
Essays on Equilibrium Computation, MDD-based Constraint Programming and Scheduling. *PhD thesis*,
Carnegie Mellon University, 2010.

S. Hoda, W.-J. van Hoeve, and J. N. Hooker.
A Systematic Approach to MDD-Based Constraint Programming.
In *Proceedings of CP*. LNCS 6308, pp. 266-280. Springer, 2010.

T. Hadzic, J. N. Hooker, B. O'Sullivan, and P. Tiedemann.
Approximate compilation of constraints into multivalued decision diagrams.
In *Proceedings of CP*. LNCS 5202, pp. 448-462. Springer, 2008.

T. Hadzic, J. N. Hooker, and P. Tiedemann.
Propagating separable equalities in an MDD store.
In *Proceedings of CPAIOR*. LNCS 5015, pp. 318-322. Springer, 2008.

H. R. Andersen, T. Hadzic, J. N. Hooker, and P. Tiedemann.
A constraint store based on multivalued decision diagrams.
In *Proceedings of CP*. LNCS 4741, pp. 118-132. Springer, 2008.

Tarik Hadzic and J. N. Hooker.
Cost-bounded binary decision diagrams for 0-1 programming.
In *Proceedings of CPAIOR*. LNCS 4510, pp. 84-98. Springer, 2007.

Tarik Hadzic and J. N. Hooker. Postoptimality analysis for integer programming using binary decision diagrams. December 2007, revised April 2008 (not submitted).

### Presentations

#### Plenary Talks and Tutorials

W.-J. van Hoeve,
Decision Diagrams for Discrete Optimization.
*
Tutorial Forum, Twenty-Seventh AAAI Conference*, 2013.

Video's:
Part 1,
Part 2,
Part 3

Solutions to the exercises can
also be downloaded.

W.-J. van Hoeve, Constraint Programming with Decision Diagrams.
*International Conference on Principles and Practice of Constraint Programming (CP)*, 2012.

W.-J. van Hoeve, Decision Diagrams for Discrete Optimization, Mixed Integer Programming (MIP) Workshop Series, 2011.

J. N. Hooker, Multivalued decision diagrams and what they can do for you.
Keynote talk, *CP Workshop on Constraint Reasoning and Graphical Structures*, 2010.

#### Other Presentations

- D. Bergman, Decision Diagrams for Discrete Optimization, INFORMS 2013, October 2013.
- A. A. Cire, Decision Diagrams for Sequencing and Scheduling, INFORMS 2013, October 2013.
- J. N. Hooker, Decision diagrams and dynamic programming, INFORMS 2013, October 2013.
- B. Kell, An MDD approach to multidimensional bin packing, CPAIOR 2013, Yorktown Heights, NY, May 2013.
- J. N. Hooker, Decision diagrams and dynamic programming, CPAIOR 2013, Yorktown Heights, NY, May 2013.
- J. N. Hooker, Optimization bounds from binary decision diagrams, Third Boolean Seminar, Liblice, Czech Republic, April 2013.
- J. N. Hooker, Optimization bounds from binary decision diagrams, ICS 2013, Santa Fe, January 2013.
- A. A. Cire, MDD Propagation for Disjunctive Scheduling, INFORMS Optimization Society Conference, 2012.
- A. A. Cire, MDD Propagation for Disjunctive Scheduling, ISMP, 2012.
- W.-J. van Hoeve, MDD Propagation for Disjunctive Scheduling, Montreal Optimization Days, 2012.
- W.-J. van Hoeve, MDD Propagation for Disjunctive Scheduling, Modeling and OPtimization: Theory and Applications (MOPTA), 2012.
- W.-J. van Hoeve, MDD Propagation for Disjunctive Scheduling, INFORMS Annual Meeting, 2012.
- W.-J. van Hoeve, MDD Propagation for Sequence Constraints, INFORMS Optimization Society Conference, 2012.
- W.-J. van Hoeve, MDD Propagation for Sequence Constraints, CPAIOR Poster Presentation, 2012.
- W.-J. van Hoeve, MDD Propagation for Sequence Constraints, INFORMS Annual Meeting, 2011.
- W.-J. van Hoeve, Decision Diagrams for Discrete Optimization, Ecole Polytechnique de Montreal; CWI Amsterdam; University of Utrecht, 2011.
- W.-J. van Hoeve, Decision Diagrams for Constraint Programming, Workshop on Constraint Modelling and Reformulation (ModRef), 2011.
- J. N. Hooker, Relaxation based on multivalued decision diagrams, INFORMS 2010, Austin, October 2010.
- J. N. Hooker, A systematic approach to MDD-based constraint programming, CP 2010, St Andrews, Scotland, September 2010.
- W.-J. van Hoeve, MDD-Based Propagation of Among Constraints, European Conference on Operational Research (EURO), 2010.
- S. Hoda, MDD-Based Propagation of Among Constraints, INFORMS Annual Meeting, 2009.
- J. N. Hooker, Propagating separable equalities in an MDD store, INFORMS 2008, Washington, October 2008.
- J. N. Hooker, Postoptimality analysis using multivalued decision diagrams, Cork Constraint Computation Centre, Ireland, June 2008.
- J. N. Hooker, Postoptimality analysis using multivalued decision diagrams, London School of Economics, June 2008.
- J. N. Hooker, Cost-bounded binary decision diagrams for 0-1 programming, INFORMS 2007, Seattle, November.
- J. N. Hooker, A constraint store based on multivalued decision diagrams, CP 2007, Providence, September. 2007
- J. N. Hooker, Cost-bounded binary decision diagrams for 0-1 programming, CPAIOR 2007, Brussels, May.
- J. N. Hooker, Integer programming with binary decision diagrams, ICS 2007, Coral Gables, January 2007.
- J. N. Hooker, Discrete global optimization with binary decision diagrams, GICOLAG, Vienna, December 2006.

### Acknowledgements

This research is supported by NSF grant CMMI 1130012, AFOSR grant FA9550-11-1-0180, and a Google Research Award.