Migration: Shortest Path (lpsole09)
/***********************************************************************/
/* */
/* S A S S A M P L E L I B R A R Y */
/* */
/* NAME: lpsole09 */
/* TITLE: Migration: Shortest Path (lpsole09) */
/* PRODUCT: OR */
/* SYSTEM: ALL */
/* KEYS: OR */
/* PROCS: OPTMODEL */
/* DATA: */
/* */
/* SUPPORT: UPDATE: */
/* REF: */
/* MISC: Example 9 from the Linear Programming Solver */
/* chapter of Mathematical Programming. */
/* */
/***********************************************************************/
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
;
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;
proc print data=spath;
sum _fcost_;
run;