Decision Diagrams for Optimization


Overview People Publications and software Presentations

Recent News

[11/13/2014] The INFORMS Annual Meeting 2014 contained three sessions with presentations on the use of decision diagrams in optimization:
Decision Diagrams in Optimization I
Decision Diagrams in Optimization II
Constraint Programming

[11/10/2014] Andre Cire has received the 2014 Student Paper Award from the INFORMS Computing Society at the INFORMS Annual Meeting 2014, for the paper Multivalued Decision Diagrams for Sequencing Problems.

[9/9/2014] David Bergman has received the Doctoral Research Award 2014 from the Association of Constraint Programmming, for his dissertation New Techniques for Discrete Optimization.

[7/28/2014] The paper MDD Propagation for Sequence Constraints is now published in the Journal of AI Research.

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

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


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


People

Faculty at Carnegie Mellon University:

Current and former PhD students:


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, and W.-J. van Hoeve. MDD Propagation for Sequence Constraints. JAIR, Volume 50, pages 697-722, 2014.

D. Bergman, A. A. Cire, W.-J. van Hoeve, and T. Yunes. BDD-Based Heuristics for Binary Optimization. Journal of Heuristics 20(2): 211-234, 2014.

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, LNCS 8451, pp. 351-367. 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.

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.

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


Acknowledgements

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