Example 6.7 Migration to OPTMODEL: Maximum Flow

The following example shows how to use PROC OPTMODEL to solve the example Maximum Flow Problem in Chapter 6: The NETFLOW Procedure in SAS/OR 12.3 User's Guide: Mathematical Programming Legacy Procedures. The input data set is the same as in that example.

```title 'Maximum Flow Problem';

data arcs;
input _from_ \$ _to_ \$ _cost_ _capac_;
datalines;
S a . .
S b . .
a c 1 7
b c 2 9
a d 3 5
b d 4 8
c e 5 15
d f 6 20
e g 7 11
f g 8 6
e h 9 12
f h 10 4
g T . .
h T . .
;
```

The following PROC OPTMODEL statements read the data sets, build the linear programming model, solve the model, and output the optimal solution to a SAS data set called `GOUT3`:

```proc optmodel;
str source = 'S';
str sink = 'T';

set <str> NODES;
num _supdem_ {i in NODES} = (if i in {source, sink} then . else 0);

set <str,str> ARCS;
num _lo_ {ARCS} init 0;
num _capac_ {ARCS} init .;
num _cost_ {ARCS} init 0;
read data arcs nomiss into ARCS=[_from_ _to_] _cost_ _capac_;
NODES = (union {<i,j> in ARCS} {i,j});

var Flow {<i,j> in ARCS} >= _lo_[i,j];
for {<i,j> in ARCS: _capac_[i,j] ne .} Flow[i,j].ub = _capac_[i,j];
max obj = sum {<i,j> in ARCS: j = sink} Flow[i,j];
con balance {i in NODES diff {source, sink}}:
sum {<(i),j> in ARCS} Flow[i,j]
- sum {<j,(i)> in ARCS} Flow[j,i] = _supdem_[i];

solve;

num _supply_ {<i,j> in ARCS} =
(if _supdem_[i] ne 0 then _supdem_[i] else .);
num _demand_ {<i,j> in ARCS} =
(if _supdem_[j] ne 0 then -_supdem_[j] else .);
num _fcost_ {<i,j> in ARCS} = _cost_[i,j] * Flow[i,j].sol;

create data gout3 from [_from_ _to_]
_cost_ _capac_ _lo_ _supply_ _demand_ _flow_=Flow _fcost_;
quit;
```

To solve a maximum flow problem, you solve a network flow problem that has a zero supply or demand at all nodes other than the source and sink nodes, as specified in the declaration of the _SUPDEM_ numeric parameter and the balance constraint. The objective declaration uses the logical condition J = SINK to maximize the flow into the sink node. The output data set is displayed in Output 6.7.1.

Output 6.7.1: Optimal Solution

Obs _from_ _to_ _cost_ _capac_ _lo_ _supply_ _demand_ _flow_ _fcost_
1 S a 0 . 0 . . 12 0
2 S b 0 . 0 . . 13 0
3 a c 1 7 0 . . 7 7
4 b c 2 9 0 . . 8 16
5 a d 3 5 0 . . 5 15
6 b d 4 8 0 . . 5 20
7 c e 5 15 0 . . 15 75
8 d f 6 20 0 . . 10 60
9 e g 7 11 0 . . 3 21
10 f g 8 6 0 . . 6 48
11 e h 9 12 0 . . 12 108
12 f h 10 4 0 . . 4 40
13 g T 0 . 0 . . 9 0
14 h T 0 . 0 . . 16 0

The log is displayed in Output 6.7.2.

Output 6.7.2: OPTMODEL Log

 NOTE: There were 14 observations read from the data set WORK.ARCS. NOTE: Problem generation will use 4 threads. NOTE: The problem has 14 variables (0 free, 0 fixed). NOTE: The problem has 8 linear constraints (0 LE, 8 EQ, 0 GE, 0 range). NOTE: The problem has 24 linear constraint coefficients. NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range). NOTE: The OPTMODEL presolver is disabled for linear problems. NOTE: The problem is a pure network instance. The ALGORITHM=NETWORK option is recommended for solving problems with this structure. NOTE: The LP presolver value AUTOMATIC is applied. NOTE: The LP presolver removed 10 variables and 6 constraints. NOTE: The LP presolver removed 20 constraint coefficients. NOTE: The presolved problem has 4 variables, 2 constraints, and 4 constraint coefficients. NOTE: The LP solver is called. NOTE: The Dual Simplex algorithm is used. Objective Phase Iteration        Value         Time D 1          1    0.000000E+00         0 D 2          2    2.500000E+01         0 P 2          5    2.500000E+01         0 P 2          6    2.500000E+01         0 NOTE: Optimal. NOTE: Objective = 25. NOTE: The Dual Simplex solve time is 0.03 seconds. NOTE: The data set WORK.GOUT3 has 14 observations and 9 variables.