The Decomposition Algorithm
Example 17.10 ATM Cash Management in Distributed Mode
This section illustrates how you can use PROC OPTMODEL and the decomposition algorithm in distributed mode. The problem is the same as the one described in Example 17.9 for managing the cash flow of a bank’s network of automated teller machines (ATMs). The only difference between single-machine and distributed mode is that the DISTRIBUTED= option is set to TRUE in the main solver statement. In this example, the CAS session is configured for 20 worker nodes, each having 32 cores.
The following statement changes the operating mode to distributed mode:
/* solve with the decomposition algorithm (in distributed mode) */
solve with milp / distributed=true nthreads=4 relobjgap=0.01 decomp;
When you specify DISTRIBUTED=TRUE and NTHREADS=4, each machine in your configured session processes the subproblems by using up to four threads simultaneously (per machine).
The solution summary is displayed in Output 17.10.1.
Output 17.10.1: Solution Summary Table
| Solution Summary | |
|---|---|
| Solver | MILP |
| Algorithm | Decomposition |
| Objective Function | CashFlowDiff |
| Solution Status | Optimal within Relative Gap |
| Objective Value | 2465948.8638 |
| Relative Gap | 0.0040134327 |
| Absolute Gap | 9857.3580513 |
| Primal Infeasibility | 9.134164E-11 |
| Bound Infeasibility | 0 |
| Integer Infeasibility | 0 |
| Best Bound | 2456091.5057 |
| Nodes | 1 |
| Solutions Found | 9 |
| Iterations | 10 |
| Presolve Time | 0.90 |
| Solution Time | 22.42 |
The iteration log, which contains the problem statistics, the progress of the solution, and the optimal objective value, is shown in Output 17.10.2.
Output 17.10.2: Log
| NOTE: There were 100 observations read from the data set WORK.BUDGET_DATA. |
| NOTE: There were 20 observations read from the data set WORK.CASHOUT_DATA. |
| NOTE: There were 2000 observations read from the data set WORK.POLYFIT_DATA. |
| NOTE: Problem generation will use 4 threads. |
| NOTE: The problem has 6480 variables (0 free, 0 fixed). |
| NOTE: The problem has 2220 binary and 0 integer variables. |
| NOTE: The problem has 4380 linear constraints (2340 LE, 2040 EQ, 0 GE, 0 range). |
| NOTE: The problem has 58878 linear constraint coefficients. |
| NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range). |
| NOTE: The SOLVE statement is executing in the distributed computing environment with 25 worker |
| nodes. |
| NOTE: The initial MILP heuristics are applied. |
| NOTE: The MILP presolver value AUTOMATIC is applied. |
| NOTE: The MILP presolver removed 562 variables and 390 constraints. |
| NOTE: The MILP presolver removed 21280 constraint coefficients. |
| NOTE: The MILP presolver modified 0 constraint coefficients. |
| NOTE: The presolved problem has 5918 variables, 3990 constraints, and 37598 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 25 |
| worker nodes. |
| NOTE: The DECOMP method value USER is applied. |
| NOTE: The problem has a decomposable structure with 20 blocks. The largest block covers 5.138% |
| of the constraints in the problem. |
| NOTE: The decomposition subproblems cover 5918 (100%) variables and 3890 (97.49%) 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 |
| NOTE: Starting phase 1. |
| 1 0.0000 1.1767 . 1.18e+00 . 6 |
| 2 0.0000 0.0000 . 0.00% . 6 |
| NOTE: Starting phase 2. |
| . 2.4432e+06 2.5908e+06 2.5944e+06 6.04% 6.19% 9 |
| 8 2.4561e+06 2.4767e+06 2.4889e+06 0.84% 1.34% 21 |
| NOTE: The Decomposition algorithm stopped on the integer RELOBJGAP= option. |
| 10 2.4561e+06 2.4640e+06 2.4659e+06 0.32% 0.40% 22 |
| Node Active Sols Best Best Gap Real |
| Integer Bound Time |
| 0 1 9 2.4659e+06 2.4561e+06 0.40% 22 |
| NOTE: The Decomposition algorithm used 4 threads. |
| NOTE: The Decomposition algorithm time is 22.42 seconds. |
| NOTE: Optimal within relative gap. |
| NOTE: Objective = 2465948.8638. |
Notice how this iteration log differs from the iteration log for single-machine mode in Example 17.9. In this case, the path is slightly altered because each block solve uses four threads (parallel branch-and-cut) to solve the subproblems as opposed to one thread (sequential branch-and-cut) when running in single-machine mode. The calculation of the default value for the NTHREADS= option in the DECOMPSUBPROB statement is described on .