You want to find the minimum number of edges that need to be duplicated to make the graph Eulerian, that is, to make every node have even degree. This problem is known as the "Chinese postman" problem or "route inspection" problem.
The following PROC OPTMODEL code (which works in both SAS 9 and SAS Viya) uses the network solver to find shortest-path distances for all pairs of odd-degree nodes and then uses the MILP solver to find an optimal matching in the complete graph of odd-degree nodes. The edges that appear in the shortest paths for the matches are the ones that should be duplicated.
proc optmodel;
/* define graph */
set <str,str> EDGES;
read data original_data into EDGES=[node_1 node_2];
put (card(EDGES))=;
set NODES = union {<i,j> in EDGES} {i,j};
put (card(NODES))=;
num deg {NODES} init 0;
for {<i,j> in EDGES} do;
deg[i] = deg[i] + 1;
deg[j] = deg[j] + 1;
end;
set ODD_NODES = {i in NODES: mod(deg[i],2) = 1};
put ODD_NODES=;
put (card(ODD_NODES))=;
/* find shortest-path distances for all pairs of odd nodes */
num spweights {ODD_NODES, ODD_NODES} init .;
solve with network /
shortpath=(source=ODD_NODES sink=ODD_NODES) links=(include=EDGES) out=(spweights=spweights);
print spweights;
set ODD_PAIRS = {i in ODD_NODES, j in ODD_NODES: i < j and spweights[i,j] ne .};
put (card(ODD_PAIRS))=;
set <str,str> ODD_PAIRS_node {ODD_NODES} init {};
for {<i,j> in ODD_PAIRS} do;
ODD_PAIRS_node[i] = ODD_PAIRS_node[i] union {<i,j>};
ODD_PAIRS_node[j] = ODD_PAIRS_node[j] union {<i,j>};
end;
/* find optimal matching in complete graph of odd nodes */
/* IsMatch[i,j] = 1 if odd pair <i,j> is matched, 0 otherwise */
var IsMatch {ODD_PAIRS} binary;
/* minimize number of duplicated edges */
min NumDuplicatedEdges = sum {<i,j> in ODD_PAIRS} spweights[i,j] * IsMatch[i,j];
/* force every odd node to be matched */
con Matching {k in ODD_NODES}:
sum {<i,j> in ODD_PAIRS_node[k]} IsMatch[i,j] = 1;
/* call MILP solver */
solve;
set MATCHES = {<i,j> in ODD_PAIRS: IsMatch[i,j].sol > 0.5};
put MATCHES=;
put (card(MATCHES))=;
/* retrieve actual shortest paths only for matched pairs */
str source, sink;
set <str,str> SP_EDGES {MATCHES};
set <str,str,num,str,str> SP_PATHS; /* <source,sink,order,from,to> */
set SOURCES = {source};
set SINKS = {sink};
reset option printlevel=0;
cofor {<i,j> in MATCHES} do;
source = i;
sink = j;
solve with network / loglevel=0
shortpath=(source=SOURCES sink=SINKS) links=(include=EDGES) out=(sppaths=SP_PATHS);
SP_EDGES[i,j] = setof {<(i),(j),order,from,to> in SP_PATHS} <from,to>;
end;
reset option printlevel=1;
/* update degrees */
set EDGES_SOL = union {<i,j> in MATCHES} SP_EDGES[i,j];
put (card(EDGES_SOL))=;
num new_deg {i in NODES} init deg[i];
for {<i,j> in EDGES_SOL} do;
new_deg[i] = new_deg[i] + 1;
new_deg[j] = new_deg[j] + 1;
end;
/* create SAS data sets */
create data node_data_out from [i]=NODES deg degmod2=(mod(deg[i],2)) new_deg;
create data edge_data_out from [i j]=EDGES_SOL;
quit;
Your network has 98 nodes (not 106) and 103 edges, and the following 8 nodes have odd degree:
ODD_NODES={'I27','I1','A20','A1','S21','S1_E27','E38','E28'}
The shortest-path distances are:
spweights
A1
A20
E28
E38
I1
I27
S1_E27
S21
A1
.
19
16
26
10
30
15
25
A20
19
.
14
24
15
22
13
15
E28
16
14
.
10
12
22
1
21
E38
26
24
10
.
22
32
11
31
I1
10
15
12
22
.
26
11
21
I27
30
22
22
32
26
.
22
31
S1_E27
15
13
1
11
11
22
.
20
S21
25
15
21
31
21
31
20
.
An optimal matching, with weight 57, is:
MATCHES={<'I27','S1_E27'>,<'A20','S21'>,<'A1','I1'>,<'E28','E38'>}
(The pair <'E28','S1_E27'> is tempting because it has weight 1, but the optimal matching that includes that pair turns out to have weight 58 > 57.)
The node_data_out data set reports both the old and new degrees, and the edge_data_out data set contains only the 57 edges that need duplication.
If you have edge weights (like distances between stations), the same approach can be used to minimize the total duplicated edge weight instead of just the number of duplicated edges.
... View more
