The Dantzig-Wolfe Decomposition Algorithm

This example demonstrates how you can use the METHOD=CONCOMP option in the DECOMP statement to run the Dantzig-Wolfe decomposition algorithm.

Consider a mixed integer linear program that is defined by the MPS data table mylib.mpsdata. In this case, the structure of the model is unknown and only the MPS data table is provided to you.

The following PROC OPTMILP statements solve the problem by using standard methods.

proc optmilp
   nthreads = 4
   data     = mylib.mpsdata;
run;

The solution summary is shown in Output 19.3.1.

The iteration log, which contains the problem statistics and the progress of the solution, is shown in Output 19.3.2.

A note in the log mentions that the problem structure is decomposable. The following PROC OPTMILP statements use the METHOD=CONCOMP option in the DECOMP statement to solve the problem using the Dantzig-Wolfe decomposition algorithm.

proc optmilp
   nthreads    = 4
   data        = mylib.mpsdata;
   decomp
      loglevel = moderate
      method   = concomp;
run;

The solution summary is displayed in Output 19.3.3.

The iteration log, which contains the problem statistics and the progress of the solution, is shown in Output 19.3.4. When you specify NTHREADS=4 in the PROC OPTMILP statement, the blocks are processed simultaneously on four threads.

In this case, the solver finds that after the presolve, the constraint matrix decomposes into block-diagonal form. That is, all the constraints are covered by subproblem blocks, leaving the set of master constraints empty. Because there are no coupling constraints, the problem decomposes into four completely independent problems. If you specify LOGLEVEL=MODERATE in the DECOMP statement, the log displays the size of each block. The blocks in this case are nicely balanced, allowing parallel execution to be efficient.