The Decomposition Algorithm
Example 18.5 Block-Angular Structure in Distributed Mode
This example demonstrates how you can use the default automated method to run the decomposition algorithm in distributed mode.
Consider again the mixed integer linear program that is defined by the MPS data table mycas.mpsdata. The following PROC OPTMILP statements run the decomposition algorithm in distributed mode. The DATA= option assumes that your CAS engine libref is named mycas, but you can substitute any appropriately defined CAS engine libref.
proc optmilp
distributed = true
nthreads = 4
data = mycas.mpsdata;
decomp
hybrid = false;
run;
The solution summary is displayed in Output 18.5.1.
Output 18.5.1: Solution Summary
| Solution Summary | |
|---|---|
| Solver | MILP |
| Algorithm | Decomposition |
| Objective Function | Total_Profit |
| Solution Status | Optimal within Relative Gap |
| Objective Value | 6972.3309348 |
| Relative Gap | 4.2763526E-9 |
| Absolute Gap | 0.0000298161 |
| Primal Infeasibility | 9.925394E-14 |
| Bound Infeasibility | 4.9788464E-8 |
| Integer Infeasibility | 9.325873E-15 |
| Best Bound | 6972.3309646 |
| Nodes | 1 |
| Solutions Found | 11 |
| Iterations | 19 |
| Presolve Time | 0.44 |
| Solution Time | 25.17 |
The iteration log, which contains the problem statistics and the progress of the solution, is shown in Output 18.5.2. When you specify DISTRIBUTED=TRUE and NTHREADS=4 in the OPTMILP statement, the blocks are processed using all the machines in your configured session (four machines in this case). Each machine uses four threads.
Output 18.5.2: Log
| NOTE: The problem MPSDATA has 52638 variables (16038 binary, 0 integer, 0 free, 0 fixed). |
| NOTE: The problem has 3949 constraints (3339 LE, 0 EQ, 610 GE, 0 range). |
| NOTE: The problem has 148866 constraint coefficients. |
| NOTE: The initial MILP heuristics are applied. |
| NOTE: The MILP presolver value AUTOMATIC is applied. |
| NOTE: The MILP presolver removed 0 variables and 734 constraints. |
| NOTE: The MILP presolver removed 17616 constraint coefficients. |
| NOTE: The MILP presolver modified 0 constraint coefficients. |
| NOTE: The presolved problem has 52638 variables, 3215 constraints, and 131250 constraint |
| coefficients. |
| NOTE: The MILP solver is called. |
| NOTE: The Decomposition algorithm is used. |
| NOTE: The Decomposition algorithm is executing in the distributed computing environment with 4 |
| worker nodes. |
| NOTE: The DECOMP method value DEFAULT is applied. |
| NOTE: The decomposition identification used 0.23 (cpu: 0.31) seconds. |
| NOTE: The problem has a decomposable structure with 610 blocks. The largest block covers |
| 0.2488% of the constraints in the problem. |
| NOTE: The decomposition subproblems cover 52638 (100%) variables and 3207 (99.75%) constraints. |
| NOTE: The deterministic parallel mode is enabled. |
| NOTE: The Decomposition algorithm is using up to 4 threads. |
| Iter Best Master Best LP IP Real |
| Bound Objective Integer Gap Gap Time |
| . 7963.9759 6473.6890 6473.2340 18.71% 18.72% 8 |
| 2 7257.8871 6473.6890 6473.2340 10.80% 10.81% 11 |
| 3 7147.8687 6883.2701 6473.2340 3.70% 9.44% 15 |
| 5 6986.0299 6960.5400 6960.5400 0.36% 0.36% 21 |
| 6 6986.0299 6965.5335 6965.5335 0.29% 0.29% 22 |
| 7 6986.0299 6972.3309 6972.3309 0.20% 0.20% 23 |
| . 6986.0299 6972.3309 6972.3309 0.20% 0.20% 24 |
| 10 6986.0299 6972.3309 6972.3309 0.20% 0.20% 24 |
| 19 6972.3310 6972.3309 6972.3309 0.00% 0.00% 25 |
| Node Active Sols Best Best Gap Real |
| Integer Bound Time |
| 0 1 11 6972.3309 6972.3310 0.00% 25 |
| NOTE: The Decomposition algorithm used 4 threads. |
| NOTE: The Decomposition algorithm time is 25.17 seconds. |
| NOTE: Optimal within relative gap. |
| NOTE: Objective = 6972.3309348. |
| NOTE: The Cloud Analytic Services server processed the request in 25.72325 seconds. |
In this case, the automated method successfully finds a decomposition that contains 610 blocks and has more than 99% subproblem coverage, as in Example 18.4.