The Decomposition Algorithm

Example 14.4 Block-Diagonal Structure and METHOD=AUTO in Distributed Mode

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

As in Example 14.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 use the METHOD=AUTO option in distributed mode. The PERFORMANCE statement specifies the number of threads and nodes to be used.

proc optmilp
   data       = mpsdata;
   decomp
     loglevel = 2
     method   = auto;
   performance
     details
     nthreads = 1
     nodes    = 4;
run;

The performance information is displayed in Output 14.4.1.

Output 14.4.1: Performance Information

Performance Information
Host Node	<< your grid host >>
Execution Mode	Distributed
Grid Mode	Symmetric
Number of Compute Nodes	4
Number of Threads per Node	1

The solution summary is displayed in Output 14.4.2.

Output 14.4.2: Solution Summary

Solution Summary
Solver	MILP
Algorithm	Decomposition
Objective Function	R0001298
Solution Status	Optimal
Objective Value	120

Relative Gap	0
Absolute Gap	0
Primal Infeasibility	9.325873E-15
Bound Infeasibility	4.662937E-15
Integer Infeasibility	0

Best Bound	120
Nodes	1
Iterations	1
Presolve Time	0.02
Solution Time	1.48

Solution Summary
Solver	MILP
Algorithm	Decomposition
Objective Function	R0001298
Solution Status	Optimal
Objective Value	120

Relative Gap	0
Absolute Gap	0
Primal Infeasibility	4.551914E-14
Bound Infeasibility	2.153833E-14
Integer Infeasibility	0

Best Bound	120
Nodes	1
Iterations	1
Presolve Time	0.02
Solution Time	0.89

The iteration log, which contains the problem statistics and the progress of the solution, is shown in Output 14.4.3. When you specify NODES=4 and NTHREADS=1 in the PERFORMANCE statement in distributed mode, each block is processed simultaneously on each of four grid nodes.

Output 14.4.3: Log

NOTE: The problem MPSDATA has 388 variables (36 binary, 0 integer, 1 free, 0 fixed).

NOTE: The problem has 1297 constraints (630 LE, 37 EQ, 630 GE, 0 range).

NOTE: The problem has 4204 constraint coefficients.

NOTE: The OPTMILP procedure is executing in the distributed computing environment

with 4 worker nodes.

NOTE: The MILP presolver value AUTOMATIC is applied.

NOTE: The MILP presolver removed 37 variables and 37 constraints.

NOTE: The MILP presolver removed 424 constraint coefficients.

NOTE: The MILP presolver modified 0 constraint coefficients.

NOTE: The presolved problem has 351 variables, 1260 constraints, and 3780 constraint

coefficients.

NOTE: The MILP solver is called.

NOTE: The Decomposition algorithm is used.

NOTE: The DECOMP method value AUTO is applied.

NOTE: The problem has a decomposable structure with 4 blocks. The largest block

covers 25.08% of the constraints in the problem.

NOTE: The decomposition subproblems cover 351 (100.00%) variables and 1260 (100.00%)

constraints.

NOTE: Block 1 has 88 (25.07%) variables and 316 (25.08%) constraints.

NOTE: Block 2 has 88 (25.07%) variables and 316 (25.08%) constraints.

NOTE: Block 3 has 88 (25.07%) variables and 316 (25.08%) constraints.

NOTE: Block 4 has 87 (24.79%) variables and 312 (24.76%) constraints.

NOTE: ------------------------------------------------------------------

NOTE: Starting to process node 0.

NOTE: ------------------------------------------------------------------

NOTE: The subproblem solver for 4 blocks at iteration 0 is starting.

NOTE: The subproblem solver for 4 blocks used 0.83 (cpu: 0.00) seconds.

NOTE: The initial column pool after generating initial variables contains 4 columns.

NOTE: The number of active nodes is 0.

NOTE: The objective value of the best integer feasible solution is 120.0000 and the

best bound is 120.0000.

NOTE: The Decomposition algorithm time is 1.40 seconds.

NOTE: Optimal.

NOTE: Objective = 120.

NOTE: The data set WORK.PERFINFO has 5 observations and 3 variables.