The Dantzig-Wolfe Decomposition Algorithm

In the special case of a set partitioning master problem and identical blocks, the underlying algorithm is automatically adjusted to reduce symmetry and improve overall performance. Identical blocks are subproblems (see the section Overview: Dantzig-Wolfe Decomposition Algorithm) that have equivalent feasible regions (and optima) when they are projected. Algebraically, this means that

A set partitioning problem is a specific type of integer programming model in which each constraint represents choosing exactly one member of a set. These constraints are often referred to as assignment constraints. The linear relaxation of a set partitioning problem enables an algorithm to choose fractional parts of several members of some set such that they sum to 1. Algebraically, this means , where all the coefficients in are 0 or 1.

The performance of algorithms that use a branch-and-bound method can suffer when the formulation contains substructures that are symmetric. In this context, symmetric means that an assignment of solutions can be arbitrarily permuted for some component without affecting the optimality of that solution. For example, if

and

are both optimal, then these solutions, , are considered symmetric on index j. That is, you can interchange and without affecting the optimality of the solution. The presence of identical blocks in a mathematical program is an obvious case in which symmetry can hurt performance. In order to overcome this handicap, the Dantzig-Wolfe decomposition algorithm aggregates the identical blocks into one block when it forms the Dantzig-Wolfe master problem. If the Dantzig-Wolfe master problem is a set partitioning model, the algorithm uses a specialized branching rule known as Ryan-Foster branching. If the original master model (after aggregation) is equivalent to the identity matrix, this guarantees that the Dantzig-Wolfe master problem is of the appropriate form. For more information about the aggregate formulation and Ryan-Foster branching, see Barnhart et al. (1998).

Suppose you want to solve the following problem:

If constraints m1 and m2 are removed, then the remaining constraints s1 and s2 decompose into two independent and identical subproblems. In addition, constraints m1 and m2 form a set partitioning master problem.

The following statements use the OPTMODEL procedure and the Dantzig-Wolfe decomposition algorithm to solve the preceding problem:

proc optmodel;
   var x{i in 1..3, j in 1..2} binary;

   max f =    x[1,1] + 2*x[2,1] +   x[3,1] +
              x[1,2] + 2*x[2,2] +   x[3,2];

   con m1:    x[1,1] +   x[1,2]             =  1;
   con m2:    x[2,1] +   x[2,2]             =  1;
   con s1:  5*x[1,1] + 7*x[2,1] + 4*x[3,1] <= 11;
   con s2:  5*x[1,2] + 7*x[2,2] + 4*x[3,2] <= 11;

   s1.block = 0;
   s2.block = 1;

   solve with milp / presolver=none decomp=(logfreq=1);
   print x;
quit;

Here, the PRESOLVER=NONE option is used again, because otherwise the presolver solves this small instance without invoking any solver. The solution summary and optimal solution are displayed in Figure 3.

The iteration log, which displays the problem statistics, the progress of the solution, and the optimal objective value, is shown in Figure 4.

The decomposition solver recognizes that the original master model is of the appropriate form and that each block is identical. It formulates the aggregate master and uses Ryan-Foster branching to solve the model.

In the presence of identical blocks, under certain circumstances, the aggregate formulation can also be used with a set covering master formulation. A set covering problem is an integer programming model in which each constraint represents choosing at least one member of a set. Algebraically, this means , where all the coefficients in are 0 or 1. Aggregate formulation and Ryan-Foster branching can be used if there exists an optimal solution, , that is binding at equality (). If you can guarantee such a condition, you can greatly improve performance by explicitly using VARSEL=RYANFOSTER as a MILP main solver option. The Dantzig-Wolfe decomposition algorithm usually performs better when it uses a set covering formulation as opposed to a set partitioning formulation, because it is usually easier to find integer feasible solutions. If the models are equivalent, using the set covering formulation is recommended. For two examples, see Example 18.6, which shows the bin packing problem, and Example 18.8, which shows the vehicle routing problem.

Similarly, a set packing problem is an integer programming model in which each constraint represents choosing at most one member of a set. Algebraically, this means , where all the coefficients in are 0 or 1. Aggregate formulation and Ryan-Foster branching can be used if there exists an optimal solution, , that is binding at equality (). In this case, using VARSEL=RYANFOSTER can improve performance. Alternatively, you can transform any set packing model into a set partitioning model by introducing a zero-cost slack variable for each packing constraint. See Example 18.11, which shows an application that optimizes a kidney donor exchange.

The Dantzig-Wolfe decomposition algorithm automatically searches for identical blocks and the appropriate set partitioning master formulation. If it finds this structure, the algorithm automatically generates the aggregate formulation and uses Ryan-Foster branching. The aggregate model needs to process only one block at each subproblem iteration. Therefore, parallel processing (in which multiple blocks are processed simultaneously), as described in the section Parallel Processing, cannot improve performance. For this reason, when the Dantzig-Wolfe decomposition algorithm runs in distributed mode, it does not create the aggregate formulation, nor does it use Ryan-Foster branching, even if the blocks are found to be identical.