The Linear Programming Solver

Example 6.9 Migration to OPTMODEL: Shortest Path

The following example shows how to use PROC OPTMODEL to solve the example Shortest Path 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 'Shortest Path Problem';
title2 'How to get Hawaiian Pineapples to a London Restaurant';

data aircost1;
   input ffrom&$13. tto&$15. _cost_;
   datalines;
Honolulu       Chicago         105
Honolulu       San Francisco    75
Honolulu       Los Angeles      68
Chicago        Boston           45
Chicago        New York         56
San Francisco  Boston           71
San Francisco  New York         48
San Francisco  Atlanta          63
Los Angeles    New York         44
Los Angeles    Atlanta          57
Boston         Heathrow London  88
New York       Heathrow London  65
Atlanta        Heathrow London  76
;

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 SPATH:

proc optmodel;
   str sourcenode = 'Honolulu';
   str sinknode = 'Heathrow London';

   set <str> NODES;
   num _supdem_ {i in NODES} = (if i = sourcenode then 1
      else if i = sinknode then -1 else 0);

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

   var Flow {<i,j> in ARCS} >= _lo_[i,j];
   min obj = sum {<i,j> in ARCS} _cost_[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] = _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 spath from [ffrom tto]
      _cost_ _capac_ _lo_ _supply_ _demand_ _flow_=Flow _fcost_
      _rcost_=(if Flow[ffrom,tto].rc ne 0 then Flow[ffrom,tto].rc else .)
      _status_=Flow.status;
quit;

The statements use both single-dimensional (NODES) and multiple-dimensional (ARCS) index sets. The ARCS index set is populated from the ffrom and tto data set variables in the READ DATA statement. To solve a shortest path problem, you solve a minimum cost network flow problem that has a supply of one unit at the source node, a demand of one unit at the sink node, and zero supply or demand at all other nodes, as specified in the declaration of the _SUPDEM_ numeric parameter. The SPATH output data set contains most of the same information as in the PROC NETFLOW example, including reduced cost and basis status. The _ANUMB_ and _TNUMB_ values do not apply here.

The PROC PRINT statements are similar to the PROC NETFLOW example:

proc print data=spath;
   sum _fcost_;
run;

The output is displayed in Output 6.9.1.

Output 6.9.1: Output Data Set

Obs ffrom tto _cost_ _capac_ _lo_ _supply_ _demand_ _flow_ _fcost_ _rcost_ _status_
1 Honolulu Chicago 105 . 0 1 . 0 0 . B
2 Honolulu San Francisco 75 . 0 1 . 0 0 . B
3 Honolulu Los Angeles 68 . 0 1 . 1 68 . B
4 Chicago Boston 45 . 0 . . 0 0 61 L
5 Chicago New York 56 . 0 . . 0 0 49 L
6 San Francisco Boston 71 . 0 . . 0 0 57 L
7 San Francisco New York 48 . 0 . . 0 0 11 L
8 San Francisco Atlanta 63 . 0 . . 0 0 37 L
9 Los Angeles New York 44 . 0 . . 1 44 . B
10 Los Angeles Atlanta 57 . 0 . . 0 0 24 L
11 Boston Heathrow London 88 . 0 . 1 0 0 . B
12 New York Heathrow London 65 . 0 . 1 1 65 . B
13 Atlanta Heathrow London 76 . 0 . 1 0 0 . B
                  177    


The log is displayed in Output 6.9.2.

Output 6.9.2: OPTMODEL Log

NOTE: There were 13 observations read from the data set WORK.AIRCOST1.          
NOTE: Problem generation will use 4 threads.                                    
NOTE: The problem has 13 variables (0 free, 0 fixed).                           
NOTE: The problem has 8 linear constraints (0 LE, 8 EQ, 0 GE, 0 range).         
NOTE: The problem has 26 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 all variables and constraints.                   
NOTE: Optimal.                                                                  
NOTE: Objective = 177.                                                          
NOTE: The data set WORK.SPATH has 13 observations and 11 variables.