The Decomposition Algorithm

Example 15.4 Block-Diagonal Structure and METHOD=CONCOMP in Distributed Mode

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

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

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

The performance information is displayed in Output 15.4.1.

Output 15.4.1: Performance Information

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

The solution summary is displayed in Output 15.4.2.

Output 15.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.492407E-14
Bound Infeasibility	1.998401E-14
Integer Infeasibility	0

Best Bound	120
Nodes	1
Iterations	1
Presolve Time	0.05
Solution Time	0.76

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 15.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 15.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 CONCOMP 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: Using a starting solution with objective value 231 to provide initial columns.

NOTE: The initial column pool using the starting solution contains 4 columns.

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

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

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

NOTE: The Decomposition algorithm stopped on the integer RELOBJGAP= option.

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 0.68 seconds.

NOTE: Optimal.

NOTE: Objective = 120.

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