PROC NETFLOW: Migration to OPTMODEL: Shortest Path

Example 6.19 Migration to OPTMODEL: Shortest Path

The following example shows how to solve Example 6.1 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 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 data 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 Example 6.1, including reduced cost and basis status. The _ANUMB_ and _TNUMB_ values do not apply here.

The PROC PRINT statements are similar to Example 6.1.

proc print data=spath;
   sum _fcost_;
run;

The output data set contains the same optimal solution as Output 6.1.1. The log is displayed in Output 6.19.1.

Output 6.19.1 OPTMODEL Log

Shortest Path Problem

How to get Hawaiian Pineapples to a London Restaurant

NOTE: There were 13 observations read from the data set WORK.AIRCOST1.

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 OPTLP presolver value AUTOMATIC is applied.

NOTE: The OPTLP presolver removed all variables and constraints.

NOTE: Optimal.

NOTE: Objective = 177.

NOTE: The data set WORK.SPATH has 13 observations and 11 variables.