The Linear Programming Solver

Example 6.5 Using the Network Simplex Solver

This example demonstrates how you can use the network simplex solver to find the minimum-cost flow in a directed graph. Consider the directed graph in Output 6.5.1, which appears in Ahuja, Magnanti, and Orlin (1993).

Output 6.5.1: Minimum Cost Network Flow Problem: Data

Minimum Cost Network Flow Problem: Data


You can use the following SAS statements to create the input data sets nodedata and arcdata:

data nodedata;
   input _node_ $ _sd_;
   datalines;
1    10
2    20
3     0
4    -5
5     0
6     0
7   -15
8   -10
;

data arcdata;
   input _tail_ $ _head_ $ _lo_ _capac_ _cost_;
   datalines;
1    4    0    15    2
2    1    0    10    1
2    3    0    10    0
2    6    0    10    6
3    4    0     5    1
3    5    0    10    4
4    7    0    10    5
5    6    0    20    2
5    7    0    15    7 
6    8    0    10    8
7    8    0    15    9
;

You can use the following call to PROC OPTMODEL to find the minimum-cost flow:

proc optmodel;
   set <str> NODES;
   num supply_demand {NODES};

   set <str,str> ARCS;
   num arcLower  {ARCS};
   num arcUpper  {ARCS};
   num arcCost   {ARCS};

   read data arcdata into ARCS=[_tail_ _head_] 
      arcLower=_lo_ arcUpper=_capac_ arcCost=_cost_;
   read data nodedata into NODES=[_node_] supply_demand=_sd_;

   var flow {<i,j> in ARCS} >= arcLower[i,j] <= arcUpper[i,j];
   min obj = sum {<i,j> in ARCS} arcCost[i,j] * flow[i,j];
   con balance {i in NODES}:
      sum {<(i),j> in ARCS} flow[i,j] - sum {<j,(i)> in ARCS} flow[j,i] 
         = supply_demand[i]; 
   solve with lp / algorithm=ns scale=none logfreq=1;
   print flow;
quit;
%put &_OROPTMODEL_;

The optimal solution is displayed in Output 6.5.2.

Output 6.5.2: Network Simplex Solver: Primal Solution Output

The OPTMODEL Procedure

Problem Summary
Objective Sense Minimization
Objective Function obj
Objective Type Linear
   
Number of Variables 11
Bounded Above 0
Bounded Below 0
Bounded Below and Above 11
Free 0
Fixed 0
   
Number of Constraints 8
Linear LE (<=) 0
Linear EQ (=) 8
Linear GE (>=) 0
Linear Range 0
   
Constraint Coefficients 22

Performance Information
Execution Mode On Client
Number of Threads 1

Solution Summary
Solver LP
Algorithm Network Simplex
Objective Function obj
Solution Status Optimal
Objective Value 270
Iterations 8
Iterations2 0
   
Primal Infeasibility 0
Dual Infeasibility 0
Bound Infeasibility 0

[1] [2] flow
1 4 10
2 1 0
2 3 10
2 6 10
3 4 5
3 5 5
4 7 10
5 6 0
5 7 5
6 8 10
7 8 0


The optimal solution is represented graphically in Output 6.5.3.

Output 6.5.3: Minimum Cost Network Flow Problem: Optimal Solution

Minimum Cost Network Flow Problem: Optimal Solution


The iteration log is displayed in Output 6.5.4.

Output 6.5.4: Log: Solution Progress

NOTE: There were 11 observations read from the data set WORK.ARCDATA.           
NOTE: There were 8 observations read from the data set WORK.NODEDATA.           
NOTE: Problem generation will use 4 threads.                                    
NOTE: The problem has 11 variables (0 free, 0 fixed).                           
NOTE: The problem has 8 linear constraints (0 LE, 8 EQ, 0 GE, 0 range).         
NOTE: The problem has 22 linear constraint coefficients.                        
NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).      
NOTE: The PRESOLVER value NONE is applied because a pure network has been found.
NOTE: The LP presolver value NONE is applied.                                   
NOTE: The LP solver is called.                                                  
NOTE: The Network Simplex algorithm is used.                                    
NOTE: The network has 8 rows (100.00%), 11 columns (100.00%), and 1 component.  
NOTE: The network extraction and setup time is 0.00 seconds.                    
                        Primal         Primal           Dual                    
      Iteration      Objective  Infeasibility  Infeasibility     Time           
              1              0     20.0000000    109.0000000     0.00           
              2              0     20.0000000    109.0000000     0.00           
              3      5.0000000     15.0000000    104.0000000     0.00           
              4      5.0000000     15.0000000    103.0000000     0.00           
              5     75.0000000     15.0000000    103.0000000     0.00           
              6     75.0000000     15.0000000     99.0000000     0.00           
              7    130.0000000     10.0000000     96.0000000     0.00           
              8    270.0000000              0              0     0.00           
NOTE: The Network Simplex solve time is 0.00 seconds.                           
NOTE: The total Network Simplex solve time is 0.00 seconds.                     
NOTE: Optimal.                                                                  
NOTE: Objective = 270.                                                          
NOTE: The PROCEDURE OPTMODEL printed pages 40-41.                               
STATUS=OK ALGORITHM=NS SOLUTION_STATUS=OPTIMAL OBJECTIVE=270                    
PRIMAL_INFEASIBILITY=0 DUAL_INFEASIBILITY=0 BOUND_INFEASIBILITY=0 ITERATIONS=8  
ITERATIONS2=0 PRESOLVE_TIME=0.00 SOLUTION_TIME=0.00                             


Now, suppose there is a budget on the flow that comes out of arc 2: the total arc cost of flow that comes out of arc 2 cannot exceed 50. You can use the following call to PROC OPTMODEL to find the minimum-cost flow:

proc optmodel;
   set <str> NODES;
   num supply_demand {NODES};

   set <str,str> ARCS;
   num arcLower  {ARCS};
   num arcUpper  {ARCS};
   num arcCost   {ARCS};

   read data arcdata into ARCS=[_tail_ _head_] 
      arcLower=_lo_ arcUpper=_capac_ arcCost=_cost_;
   read data nodedata into NODES=[_node_] supply_demand=_sd_;

   var flow {<i,j> in ARCS} >= arcLower[i,j] <= arcUpper[i,j];
   min obj = sum {<i,j> in ARCS} arcCost[i,j] * flow[i,j];
   con balance {i in NODES}:
      sum {<(i),j> in ARCS} flow[i,j] - sum {<j,(i)> in ARCS} flow[j,i] 
         = supply_demand[i]; 
   con budgetOn2:
      sum {<i,j> in ARCS: i='2'} arcCost[i,j] * flow[i,j] <= 50;
   solve with lp / algorithm=ns scale=none logfreq=1;
   print flow;
quit;
%put &_OROPTMODEL_;

The optimal solution is displayed in Output 6.5.5.

Output 6.5.5: Network Simplex Solver: Primal Solution Output

The OPTMODEL Procedure

Problem Summary
Objective Sense Minimization
Objective Function obj
Objective Type Linear
   
Number of Variables 11
Bounded Above 0
Bounded Below 0
Bounded Below and Above 11
Free 0
Fixed 0
   
Number of Constraints 9
Linear LE (<=) 1
Linear EQ (=) 8
Linear GE (>=) 0
Linear Range 0
   
Constraint Coefficients 24

Performance Information
Execution Mode On Client
Number of Threads 1

Solution Summary
Solver LP
Algorithm Network Simplex
Objective Function obj
Solution Status Optimal
Objective Value 274
Iterations 5
Iterations2 5
   
Primal Infeasibility 8.881784E-16
Dual Infeasibility 0
Bound Infeasibility 0

[1] [2] flow
1 4 12
2 1 2
2 3 10
2 6 8
3 4 3
3 5 7
4 7 10
5 6 2
5 7 5
6 8 10
7 8 0


The optimal solution is represented graphically in Output 6.5.6.

Output 6.5.6: Minimum Cost Network Flow Problem: Optimal Solution (with Budget Constraint)

Minimum Cost Network Flow Problem: Optimal Solution (with Budget Constraint)


The iteration log is displayed in Output 6.5.7. Note that the network simplex solver extracts a subnetwork in this case.

Output 6.5.7: Log: Solution Progress

NOTE: There were 11 observations read from the data set WORK.ARCDATA.           
NOTE: There were 8 observations read from the data set WORK.NODEDATA.           
NOTE: Problem generation will use 4 threads.                                    
NOTE: The problem has 11 variables (0 free, 0 fixed).                           
NOTE: The problem has 9 linear constraints (1 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 LP presolver value AUTOMATIC is applied.                              
NOTE: The LP presolver removed 6 variables and 7 constraints.                   
NOTE: The LP presolver removed 15 constraint coefficients.                      
NOTE: The presolved problem has 5 variables, 2 constraints, and 9 constraint    
      coefficients.                                                             
NOTE: The LP solver is called.                                                  
NOTE: The Network Simplex algorithm is used.                                    
NOTE: The network has 1 rows (50.00%), 5 columns (100.00%), and 1 component.    
NOTE: The network extraction and setup time is 0.00 seconds.                    
                        Primal         Primal           Dual                    
      Iteration      Objective  Infeasibility  Infeasibility     Time           
              1    259.9800000      5.0200000     34.0000000     0.00           
              2    264.9900000      0.0100000     31.0000000     0.00           
              3    265.0300000              0      2.0000000     0.00           
              4    255.0300000              0              0     0.00           
              5    270.0000000              0              0     0.00           
NOTE: The Network Simplex solve time is 0.00 seconds.                           
NOTE: The total Network Simplex solve time is 0.00 seconds.                     
NOTE: Optimal.                                                                  
NOTE: Objective = 270.                                                          
NOTE: The Dual Simplex algorithm is used.                                       
                           Objective                Entering           Leaving  
      Phase Iteration        Value         Time     Variable           Variable 
       D 2          1    2.700000e+02         0   flow['5','6']                 
      budgetOn2 (S)                                                             
       D 2          2    2.700000e+02         0   flow['3','4']                 
      flow['2','3']                                                             
       D 2          3    2.740000e+02         0                                 
       P 2          4    2.740000e+02         0                                 
       P 2          5    2.740000e+02         0                                 
NOTE: Optimal.                                                                  
NOTE: Objective = 274.                                                          
NOTE: The Simplex solve time is 0.00 seconds.                                   
NOTE: The PROCEDURE OPTMODEL printed pages 47-48.                               
STATUS=OK ALGORITHM=NS SOLUTION_STATUS=OPTIMAL OBJECTIVE=274                    
PRIMAL_INFEASIBILITY=8.881784E-16 DUAL_INFEASIBILITY=0 BOUND_INFEASIBILITY=0    
ITERATIONS=5 ITERATIONS2=5 PRESOLVE_TIME=0.00 SOLUTION_TIME=0.00