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