Examples from the Details section (netsld01)
/***************************************************************/
/* */
/* S A S S A M P L E L I B R A R Y */
/* */
/* NAME: netsld01 */
/* TITLE: Examples from the Details section (netsld01) */
/* PRODUCT: OR */
/* SYSTEM: ALL */
/* KEYS: OR */
/* PROCS: OPTMODEL, PRINT, SORT, TRANSPOSE */
/* DATA: */
/* */
/* SUPPORT: UPDATE: */
/* REF: Examples from the Details section of the */
/* network solver documentation. */
/* MISC: */
/* */
/***************************************************************/
/* GRAPH INPUT DATA */
/* Link Input Data */
data LinkSetIn;
input from $ to $ weight @@;
datalines;
A B 1 A C 2 A D 4 B C 1 B E 2
B F 5 C E 1 D E 1 E D 1 E F 2
F G 6 G H 1 G I 1 H G 2 H I 3
;
proc optmodel;
set<str,str> LINKS;
set NODES = union{<ni,nj> in LINKS} {ni,nj};
num weight{LINKS};
read data LinkSetIn into LINKS=[from to] weight;
print weight;
put NODES=; /* computed automatically by OPTMODEL */
quit;
proc optmodel;
set NODES = 1..5;
set LINKS = {vi in NODES, vj in NODES: vi < vj};
num distance {<vi,vj> in LINKS} = 10*vi + vj;
set <num,num> TOUR;
/* Build a link set using only nodes 1..4 nodes */
set <num,num> LINKS_BETWEEN_1234 = {vi in 1..3, vj in (vi+1)..4};
/* Build a node subset consisting of nodes 3..5 */
set NODES_345 = 3..5;
/* Implicit network 1: solve over nodes 1..5 -- The original network*/
solve with NETWORK /
links=( weight=distance )
out=( tour=TOUR )
tsp
;
put TOUR=;
/* Filter on LINKS: solve over nodes 1..4 */
solve with NETWORK /
links=( weight=distance )
subgraph=( links=LINKS_BETWEEN_1234 )
out=( tour=TOUR )
tsp
;
put TOUR=;
/* Filter on NODES: solve over nodes 3..5 */
solve with NETWORK /
links=( weight=distance )
subgraph=( nodes=NODES_345 )
out=( tour=TOUR )
tsp
;
put TOUR=;
/* Explicit nodes and links: semantic error over nodes 1..5
* Links <u,5> are undefined and no documented default exists. */
solve with NETWORK /
links=( weight=distance )
subgraph=( nodes=NODES_345 links=LINKS_BETWEEN_1234 )
out=( tour=TOUR )
tsp
;
/* make room for tail, head, and weight */
set<num,num,num> LINKS_OUT;
solve with NETWORK /
links=( weight=distance )
subgraph=( nodes=NODES_345 links=LINKS_BETWEEN_1234 )
out=( tour=TOUR links=LINKS_OUT )
tsp
;
put LINKS_OUT=;
quit;
/* BICONNECTED COMPONENTS AND ARTICULATION POINTS */
data LinkSetInBiCC;
input from $ to $ @@;
datalines;
A B A F A G B C B D
B E C D E F G I G H
H I
;
proc optmodel;
set<str,str> LINKS;
read data LinkSetInBiCC into LINKS=[from to];
set NODES = union{<i,j> in LINKS} {i,j};
num bicomponent{LINKS};
set<str> ARTPOINTS;
solve with NETWORK /
loglevel = moderate
links = (include=LINKS)
biconcomp
out = (biconcomp=bicomponent artpoints=ARTPOINTS)
;
print bicomponent;
put ARTPOINTS;
create data LinkSetOut from [from to] biconcomp=bicomponent;
create data NodeSetOut from [node]=ARTPOINTS artpoint=1;
quit;
proc print data=LinkSetOut noobs label;
run;
proc print data=NodeSetOut noobs label;
run;
/* CLIQUE */
data LinkSetIn;
input from to @@;
datalines;
0 1 0 2 0 3 0 4 0 5
0 6 1 2 1 3 1 4 2 3
2 4 2 5 2 6 2 7 2 8
3 4 5 6 7 8 8 9
;
proc optmodel;
set<num,num> LINKS;
read data LinkSetIn into LINKS=[from to];
set<num,num> CLIQUES;
solve with NETWORK /
links = (include=LINKS)
clique
out = (cliques=CLIQUES)
;
put CLIQUES;
create data Cliques from [clique node]=CLIQUES;
num num_cliques = card(setof {<cid,node> in CLIQUES} cid);
set CLIQUE_IDS = 1..num_cliques;
num size {cid in CLIQUE_IDS} = card(slice(<cid,*>, CLIQUES));
create data CliqueSizes from [clique] size;
quit;
proc print data=Cliques noobs label;
run;
proc print data=CliqueSizes noobs label;
run;
/* CONNECTED COMPONENTS */
/* Connected Components of a Simple Undirected Graph */
data LinkSetIn;
input from $ to $ @@;
datalines;
A B A C B C C H D E D F D G F E G I K L
;
proc optmodel;
set<str,str> LINKS;
read data LinkSetIn into LINKS=[from to];
set NODES = union {<i,j> in LINKS} {i,j};
num component{NODES};
solve with NETWORK /
links = (include=LINKS)
concomp
out = (concomp=component)
;
print component;
create data NodeSetOut from [node] concomp=component;
quit;
proc print data=NodeSetOut noobs label;
run;
data NodeSetIn;
input node $ @@;
datalines;
A B C D E F G H I J K L
;
proc optmodel;
set<str,str> LINKS;
read data LinkSetIn into LINKS=[from to];
set<str> NODES;
read data NodeSetIn into NODES=[node];
num component{NODES};
solve with NETWORK /
links = (include=LINKS)
nodes = (include=NODES)
concomp
out = (concomp=component)
;
print component;
create data NodeSetOut from [node] concomp=component;
quit;
proc print data=NodeSetOut noobs label;
run;
/* Connected Components of a Simple Directed Graph */
data LinkSetIn;
input from $ to $ @@;
datalines;
A B B C B E B F C G
C D D C D H E A E F
F G G F H G H D
;
proc optmodel;
set<str,str> LINKS;
read data LinkSetIn into LINKS=[from to];
set NODES = union {<i,j> in LINKS} {i,j};
num component{NODES};
solve with NETWORK /
graph_direction = directed
links = (include=LINKS)
concomp
out = (concomp=component)
;
print component;
create data NodeSetOut from [node] concomp=component;
quit;
proc print data=NodeSetOut noobs label;
run;
/* CYCLE */
data LinkSetIn;
input from $ to $ @@;
datalines;
A B A E B C C A C D
D E D F E B E C F E
;
proc optmodel;
set<str,str> LINKS;
read data LinkSetIn into LINKS=[from to];
set<num,num,str> CYCLES;
solve with NETWORK /
graph_direction = directed
links = (include=LINKS)
cycle = (mode=first_cycle)
;
quit;
proc optmodel;
set<str,str> LINKS;
read data LinkSetIn into LINKS=[from to];
set<num,num,str> CYCLES;
solve with NETWORK /
graph_direction = directed
links = (include=LINKS)
cycle = (mode=all_cycles)
;
quit;
proc optmodel;
set<str,str> LINKS;
read data LinkSetIn into LINKS=[from to];
set<num,num,str> CYCLES;
solve with NETWORK /
graph_direction = directed
links = (include=LINKS)
cycle = (mode=first_cycle)
out = (cycles=CYCLES)
;
put CYCLES;
create data Cycles from [cycle order node]=CYCLES;
quit;
proc print data=Cycles noobs label;
run;
proc optmodel;
set<str,str> LINKS;
read data LinkSetIn into LINKS=[from to];
set<num,num,str> CYCLES;
solve with NETWORK /
graph_direction = directed
links = (include=LINKS)
cycle = (mode=all_cycles)
out = (cycles=CYCLES)
;
put CYCLES;
create data Cycles from [cycle order node]=CYCLES;
quit;
proc print data=Cycles noobs label;
run;
/* MINIMUM-COST NETWORK FLOW */
data LinkSetIn;
input from to weight upper;
datalines;
1 4 2 15
2 1 1 10
2 3 0 10
2 6 6 10
3 4 1 5
3 5 4 10
4 7 5 10
5 6 2 20
5 7 7 15
6 8 8 10
7 8 9 15
;
data NodeSetIn;
input node weight;
datalines;
1 10
2 20
4 -5
7 -15
8 -10
;
proc optmodel;
set <num,num> LINKS;
num cost{LINKS};
num upper{LINKS};
read data LinkSetIn into LINKS=[from to] cost=weight upper;
set NODES = union {<i,j> in LINKS} {i,j};
num supply{NODES} init 0;
read data NodeSetIn into [node] supply=weight;
num flow{LINKS};
solve with network /
loglevel = moderate
logfreq = 1
graph_direction = directed
links = (upper=upper weight=cost)
nodes = (weight=supply)
mcf
out = (flow=flow)
;
print flow;
create data LinkSetOut from [from to] upper cost flow;
quit;
proc print data=LinkSetOut label;
run;
/* MINIMUM CUT */
data LinkSetIn;
input from to weight @@;
datalines;
1 2 2 1 5 3 2 3 3 2 5 2 2 6 2
3 4 4 3 7 2 4 7 2 4 8 2 5 6 3
6 7 1 7 8 3
;
proc optmodel;
set<num,num> LINKS;
num weight{LINKS};
read data LinkSetIn into LINKS=[from to] weight;
set<num> NODES = union {<i,j> in LINKS} {i,j};
set<num,num> PARTITIONS;
set<num,num,num> CUTSETS;
solve with NETWORK /
loglevel = moderate
links = (weight=weight)
mincut = (maxnumcuts=3)
out = (partitions=PARTITIONS cutsets=CUTSETS)
;
put PARTITIONS;
put CUTSETS;
set CUTS = setof {<cut,i,j> in CUTSETS} cut;
num minCutWeight {cut in CUTS} = sum {<(cut),i,j> in CUTSETS} weight[i,j];
print minCutWeight;
create data MinCut from [mincut from to]=CUTSETS weight[from,to];
num mincut {cut in CUTS, node in NODES} =
if <cut,node> in PARTITIONS then 0 else 1;
print mincut;
create data NodeSetOut from [node]=NODES
{cut in CUTS} <col('mincut_'||cut)=mincut[cut,node]>;
quit;
proc print data=NodeSetOut noobs label;
run;
proc print data=MinCut noobs label;
run;
proc print data=MinCut noobs label;
sum weight;
by mincut;
run;
/* MINIMUM SPANNING TREE */
data LinkSetIn;
input from $ to $ weight @@;
datalines;
A B 7 A D 5 B C 8 B D 9 B E 7
C E 5 D E 15 D F 6 E F 8 E G 9
F G 11 H I 1 I J 3 H J 2
;
proc optmodel;
set<str,str> LINKS;
num weight{LINKS};
read data LinkSetIn into LINKS=[from to] weight;
set<str,str> FOREST;
solve with NETWORK /
links = (weight=weight)
minspantree
out = (forest=FOREST)
;
put FOREST;
create data MinSpanForest from [from to]=FOREST weight;
quit;
proc print data=MinSpanForest noobs label;
sum weight;
run;
/* SHORTEST PATH */
/* Shortest Paths for All Pairs */
data LinkSetIn;
input from $ to $ weight @@;
datalines;
A B 3 A C 2 A D 6 A E 4 B D 5
B F 5 C E 1 D E 2 D F 1 E F 4
;
proc optmodel;
set <str,str> LINKS;
num weight{LINKS};
read data LinkSetIn into LINKS=[from to] weight;
set <str,str,num,str,str> PATHS; /* source, sink, order, from, to */
set NODES = union{<i,j> in LINKS} {i,j};
num path_length{NODES, NODES};
solve with NETWORK /
links = (weight=weight)
shortpath
out = (sppaths=PATHS spweights=path_length)
;
put PATHS;
print path_length;
create data ShortPathP from [source sink order from to]=PATHS
weight[from,to];
create data ShortPathW from [source sink]
path_weight=path_length;
quit;
title 'ShortPathP';
proc print data=ShortPathP noobs label;
run;
title 'ShortPathW';
proc print data=ShortPathW noobs label;
run;
proc optmodel;
set <str,str> LINKS;
num weight{LINKS};
read data LinkSetIn into LINKS=[from to] weight;
set <str,str,num,str,str> PATHS; /* source, sink, order, from, to */
solve with NETWORK /
links = ( weight = weight )
shortpath = ( paths = longest )
out = ( sppaths = PATHS )
;
put PATHS;
create data ShortPathLong from [source sink order from to]=PATHS
weight[from,to];
quit;
title 'ShortPathLong';
proc print data=ShortPathLong noobs label;
run;
/* Shortest Paths for a Subset of Source-Sink Pairs */
proc optmodel;
set <str,str> LINKS;
num weight{LINKS};
read data LinkSetIn into LINKS=[from to] weight;
set <str,str,num,str,str> PATHS; /* source, sink, order, from, to */
set SOURCES = / A C /;
set SINKS = / B F /;
solve with NETWORK /
links = (weight=weight)
shortpath = (source=SOURCES sink=SINKS)
out = (sppaths=PATHS)
;
put PATHS;
create data ShortPath from [source sink order from to]=PATHS weight[from,to];
quit;
title 'ShortPath';
proc print data=ShortPath noobs label;
run;
/* Shortest Paths for a Subset of Source or Sink Pairs */
proc optmodel;
set <str,str> LINKS;
num weight{LINKS};
read data LinkSetIn into LINKS=[from to] weight;
set <str,str,num,str,str> PATHS; /* source, sink, order, from, to */
set SOURCES = / B E /;
solve with NETWORK /
links = (weight=weight)
shortpath = (source=SOURCES)
out = (sppaths=PATHS)
;
put PATHS;
create data ShortPath from [source sink order from to]=PATHS weight[from,to];
quit;
title 'ShortPath';
proc print data=ShortPath noobs label;
run;
proc optmodel;
set <str,str> LINKS;
num weight{LINKS};
read data LinkSetIn into LINKS=[from to] weight;
set <str,str,num,str,str> PATHS; /* source, sink, order, from, to */
set SINKS = / B E /;
solve with NETWORK /
links = (weight=weight)
shortpath = (sink=SINKS)
out = (sppaths=PATHS)
;
put PATHS;
create data ShortPath from [source sink order from to]=PATHS weight[from,to];
quit;
title 'ShortPath';
proc print data=ShortPath noobs label;
run;
/* Shortest Paths for One Source-Sink Pair */
proc optmodel;
set <str,str> LINKS;
num weight{LINKS};
read data LinkSetIn into LINKS=[from to] weight;
set <str,str,num,str,str> PATHS; /* source, sink, order, from, to */
set SOURCES = / C /;
set SINKS = / F /;
solve with NETWORK /
links = (weight=weight)
shortpath = (source=SOURCES sink=SINKS)
out = (sppaths=PATHS)
;
put PATHS;
create data ShortPath from [source sink order from to]=PATHS weight[from,to];
quit;
title 'ShortPath';
proc print data=ShortPath noobs label;
run;
data LinkSetIn;
input from $ to $ weight count @@;
datalines;
A B 3 1 A C 2 1 A D 6 1 A E 4 1 B D 5 1
B F 5 1 C E 1 1 D E 2 1 D F 1 1 E F 4 1
;
proc optmodel;
set <str,str> LINKS;
num weight{LINKS};
num count{LINKS};
read data LinkSetIn into LINKS=[from to] weight count;
set <str,str,num,str,str> PATHS; /* source, sink, order, from, to */
set NODES = union{<i,j> in LINKS} {i,j};
num path_length{NODES, NODES};
solve with NETWORK /
links = (weight=weight)
shortpath
out = (sppaths=PATHS spweights=path_length)
;
put PATHS;
num path_weight2{source in NODES, sink in NODES} =
sum {<(source),(sink),order,from,to> in PATHS} count[from,to];
print path_length path_weight2;
create data ShortPathW from [source sink]
path_weight=path_length path_weight2;
quit;
title 'ShortPathW';
proc print data=ShortPathW noobs label;
run;
/* TRANSITIVE CLOSURE */
data LinkSetIn;
input from $ to $ @@;
datalines;
B C B D C B D A D C
;
proc optmodel;
set<str,str> LINKS;
read data LinkSetIn into LINKS=[from to];
set<str,str> CAN_REACH;
solve with NETWORK /
links = ( include = LINKS )
transc
out = ( closure = CAN_REACH )
;
put CAN_REACH;
create data TransClosure from [from to]=CAN_REACH;
quit;
title 'Transitive Closure';
proc print data=TransClosure noobs label;
run;
/* TRAVELING SALESMAN PROBLEM */
data LinkSetIn;
input from $ to $ weight @@;
datalines;
A B 1.0 A C 1.0 A D 1.5 B C 2.0 B D 4.0
B E 3.0 C D 3.0 C F 3.0 C H 4.0 D E 1.5
D F 3.0 D G 4.0 E F 1.0 E G 1.0 F G 2.0
F H 4.0 H I 3.0 I J 1.0 C J 5.0 F J 3.0
F I 1.0 H J 1.0
;
proc optmodel;
set<str,str> EDGES;
set<str> NODES = union{<i,j> in EDGES} {i,j};
num weight{EDGES};
read data LinkSetIn into EDGES=[from to] weight;
num tsp_order{NODES};
set<str,str> TOUR;
solve with NETWORK /
loglevel = moderate
links = (weight=weight)
tsp
out = (order=tsp_order tour=TOUR)
;
put TOUR;
print {<i,j> in TOUR} weight;
print tsp_order;
create data NodeSetOut from [node] tsp_order;
create data TSPTour from [from to]=TOUR weight;
quit;
title 'Traveling Salesman Problem';
proc sort data=NodeSetOut;
by tsp_order;
run;
proc print data=NodeSetOut noobs label;
run;
proc print data=TSPTour noobs label;
sum weight;
run;