The Dantzig-Wolfe Decomposition Algorithm

This example demonstrates how you can use the default automated method to run the Dantzig-Wolfe decomposition algorithm in single-machine mode.

As in Example 18.3, 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 attempt to solve the problem by using standard methods and a 120-second time limit.

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

The solution summary is shown in Output 18.4.1.

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

Standard MILP techniques struggle to solve the problem within the specified time limit. The default decomposition method attempts to find a block-angular structure by using the matrix-stretching techniques that are described in Grcar (1990) and Aykanat, Pinar, and Çatalyürek (2004) and techniques that are based on community detection and described in Khaniyev, Elhedhli, and Erenay (2018).

proc optmilp
   nthreads  = 4
   data      = mylib.mpsdata;
   decomp
      hybrid = false;
run;

The solution summary is displayed in Output 18.4.3.

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

As stated in the log, the algorithm successfully finds a decomposition that contains 610 blocks and has more than 99% subproblem coverage.