The NETFLOW Procedure


Example 6.17 Migration to OPTMODEL: Maximum Flow

The following example shows how to solve Example 6.10 using PROC OPTMODEL. The input data set is the same as in that example.

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 contains the same optimal solution as Output 6.10.3. The log is displayed in Output 6.17.1.

Output 6.17.1: 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                                 
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.