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?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ Does this in any way relate to DMN (Decision Model Notation)? $\endgroup$– Geoffrey De SmetCommented Jun 4, 2019 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 TrickCommented Jun 4, 2019 at 19:17
-
4$\begingroup$ Plop down the $64.99 springer.com/us/book/9783319428475 and see if it says. $\endgroup$– Mark L. StoneCommented Jun 5, 2019 at 1:02
-
5$\begingroup$ ... or hope that one of the authors will tell us for free! $\endgroup$– Michael TrickCommented Jun 5, 2019 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 SchwarzCommented Jun 6, 2019 at 8:05
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
2
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:
Sequencing and routing problems. For example, single machine scheduling with setup times, time windows, and/or precedence constraints, which can also be applied to constrained traveling salesperson problems. A similar decision diagram representation was used by Grubhub to solve pickup-and-delivery problems.
Decomposition and embedding in MIP models. Decision diagrams have been used to represent subproblems in MIP models that are otherwise difficult to linearize. For example, to represent nonlinear objective functions, constrained employee schedules, or nonlinear circuit design. DDs have also been used in column generation.
Graph-theoretic problems. Examples include set covering, maximum independent set, and maximum cut.
Constraint programming. Constraint propagation based on (relaxed) decision diagrams can be much more effective than propagating domains of individual variables. This was first demonstrated on overlapping alldifferent constraints.
answered Jun 11, 2019 at 21:57
-
2$\begingroup$ Hm, your first sentence is actually a number one advertiser for MIPs as well :) $\endgroup$ Commented Jun 12, 2019 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$ Commented Jun 12, 2019 at 14:00
$\begingroup$
$\endgroup$
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).
