The Decomposition Algorithm

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

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

proc optmilp
   maxtime = 60
   data    = mpsdata;
run;

The solution summary is shown in Output 15.5.1.

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

Standard MILP techniques struggle to find a feasible solution within the specified time limit. The default decomposition method (METHOD=AUTO) 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).

proc optmilp
   data     = mpsdata;
   decomp
     method = auto;
run;

The solution summary is displayed in Output 15.5.3.

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

As stated in the log, the automated method attempts to find a balanced block-angular form that contains four blocks (the same setting is used by default in the NTHREADS= option). The algorithm successfully finds such a decomposition and then further decomposes each block into its weakly connected components, resulting in 610 blocks and 99.78% subproblem coverage.