29
$\begingroup$

Decision Diagrams are a relatively new approach to solving difficult combinatorial optimization problems. See http://www.andrew.cmu.edu/user/vanhoeve/mdd/ for some information on this approach. Are there any general rules that can help identify when MDDs or similar approaches will be successful or unsuccessful?

$\endgroup$
6
  • $\begingroup$ Does this in any way relate to DMN (Decision Model Notation)? $\endgroup$ – Geoffrey De Smet Jun 4 '19 at 19:13
  • 3
    $\begingroup$ It does not relate to DMN (an interesting approach for a complely different issue). Maybe en.wikipedia.org/wiki/Binary_decision_diagram is the right place to start on this. $\endgroup$ – Michael Trick Jun 4 '19 at 19:17
  • 3
    $\begingroup$ Plop down the $64.99 springer.com/us/book/9783319428475 and see if it says. $\endgroup$ – Mark L. Stone Jun 5 '19 at 1:02
  • 5
    $\begingroup$ ... or hope that one of the authors will tell us for free! $\endgroup$ – Michael Trick Jun 5 '19 at 1:20
  • 1
    $\begingroup$ I vaguely remember a talk at CPAIOR where it was argued that Decisions Diagrams work great if many of the nodes can be merged without losing a lot in terms of bounds. In the example applications this occured because of symmetry in the problem, I think. $\endgroup$ – Robert Schwarz Jun 6 '19 at 8:05
24
$\begingroup$

Decision diagrams (DDs) are most effective when they can compactly represent a large (perhaps exponential) set of solutions. This is done by merging equivalent states in each layer. To make decision diagrams scalable, we can use relaxed decision diagrams which allow merging nodes that are not necessarily equivalent. Relaxed decision diagrams provide dual bounds on the objective function -- a larger width can produce a stronger bound.

The relationship between the size of the decision diagram and the underlying combinatorial structure of the problem is well studied in the computer science literature; see for example the textbook by Wegener. The most important feature that influences the size is the variable ordering. We can use this to come up with some general guidelines on when a DD may be successful for combinatorial optimization:

  • The problem has a sequential structure, and decisions for stage $i$ depend only on the decisions made in stages $i-k$ through $i-1$, for small $k$.
  • The induced width of the constraint graph of the problem is small.
  • For a MIP model, the constraint matrix has a small bandwidth.
  • For knapsack-like problems, the maximum `budget' is relatively small.

Note that in some of the above cases, precise characterization of 'small' may yield (pseudo-)polynomial bounds on the size of the exact DD. In practice, relaxed DDs will always have polynomial size.

There are several areas of combinatorial optimization in which decision diagrams have been successfully applied:

$\endgroup$
2
  • 2
    $\begingroup$ Hm, your first sentence is actually a number one advertiser for MIPs as well :) $\endgroup$ – Marco Lübbecke Jun 12 '19 at 9:42
  • 3
    $\begingroup$ Yes, agreed :) The difference is that MIP models require a possibly exponential search to find solutions, while DDs list all solutions as paths which can be accessed in linear time. I like John Hooker's perspective: MIP models provide an opaque description of the solution set, while DDs are transparent -- see these slides on post-optimality analysis. $\endgroup$ – Willem-Jan van Hoeve Jun 12 '19 at 14:00
14
$\begingroup$

I am currently working with decision diagrams (DDs). From my experience, DD-based optimization works well for problems on which a recursive formulation can be exploited (i.e., problems that have a dynamic programming model).

For instance, it is the case for the maximum independent set problem and the maximum cut problem. It is also the case for some sequencing and scheduling problems.

On the reference website, you can find many problems where DDs work well (This talk presents some problems with computational results).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.