The Decomposition Algorithm

This example demonstrates how you can use the METHOD=AUTO option in the DECOMP statement to execute the decomposition algorithm in single-machine mode.

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

The following PROC OPTMILP statements solves the problem by using standard methods:

proc optmilp
   data = mpsdata;
run;

The solution summary is shown in Output 14.3.1.

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

A note in the log suggests that you can use the decomposition algorithm because of the structure of the problem. The following PROC OPTMILP statements use the METHOD=AUTO option in the DECOMP statement in single-machine mode. The PERFORMANCE statement specifies the number of threads to be used.

proc optmilp
   data       = mpsdata;
   decomp
     loglevel = 2
     method   = auto;
   subprob
     loglevel = 2;
   performance
     nthreads = 4;
run;

The performance information and solution summary are displayed in Output 14.3.3.

The iteration log, which contains the problem statistics and the progress of the solution, is shown in Output 14.3.4. When you specify NTHREADS=4 in the PERFORMANCE statement in single-machine mode, each block is processed simultaneously on each of four threads.

In this case, the solver found that, after presolve, the constraint matrix decomposed into block-diagonal form. That is, all the constraints are covered by subproblem blocks, leaving the set of master constraints empty. With no coupling constraints, the problem decomposes into four completely independent problems. If you specify LOGLEVEL=2 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.