Example 7.17 Migration to OPTMODEL: Maximum Flow

The following example shows how to solve Example 7.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 7.10.3. The log is displayed in Output 7.17.1.

Output 7.17.1: OPTMODEL Log

Maximum Flow Problem

NOTE: There were 14 observations read from the data set WORK.ARCS.              
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 OPTLP presolver value AUTOMATIC is applied.                           
NOTE: The OPTLP presolver removed 10 variables and 6 constraints.               
NOTE: The OPTLP presolver removed 20 constraint coefficients.                   
NOTE: The presolved problem has 4 variables, 2 constraints, and 4 constraint    
      coefficients.                                                             
NOTE: The DUAL SIMPLEX solver is called.                                        
                       Objective                                                
      Phase Iteration  Value                                                    
        2           1     25.000000                                             
        2           2     25.000000                                             
NOTE: Optimal.                                                                  
NOTE: Objective = 25.                                                           
NOTE: The data set WORK.GOUT3 has 14 observations and 9 variables.