The following example shows how to use PROC OPTMODEL to solve the example “Maximum Flow Problem” in Chapter 7: The NETFLOW Procedure in SAS/OR 12.1 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
Maximum Flow Problem |
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
Maximum Flow Problem |
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 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.00 seconds. |
NOTE: The data set WORK.GOUT3 has 14 observations and 9 variables. |
NOTE: The PROCEDURE OPTMODEL printed pages 58-59. |