I use MiniZinc compute a problem of optimization of shortest path problem based on hakank's model in http://www.hakank.org/minizinc
I input the distance matrix to a symmetric one such that the graph is bidirectional.
int: start = 2; % start node
int: end = 1; % end node
int: M = 999; % large number
array[1..n, 1..n] of 0..M: d = array2d(1..n,1..n,
[ M, 11, 8, 3, 8, 10, 2, 4, % 1-X
11, M, 3, 5, 1, 4, 8, 3, % 2-X
8, 3, M, 5, 7, 7, 11, 4, % 3-X
3, 5, 5, M, 9, 3, 10, 15, % 4-X
8, 6, 7, 9, M, 7, 12, 1, % 5-X
10, 4, 7, 3, 7, M, 6, 9, % 6-X
2, 8, 8, 10, 12, 9, M, 14, % 7-X
4, 3, 4, 15, 1, 9, 14, M % 8-X
]
);
% objective to minimize
var int: total_cost = sum(i in 1..n, j in 1..n where d[i,j] < M) ( d[i,j]*x[i,j] );
array[1..n] of var -1..1: rhs; % indicating start/end nodes
array[1..n, 1..n] of var 0..1: x; % the resulting connection matrix
array[1..n, 1..n] of var 0..n*n: y; % output node matrix
array[1..n] of var 0..1: outFlow; % out flow array
array[1..n] of var 0..1: inFlow; % in flow array
constraint
% set rhs for start/end nodes
forall(i in 1..n) (
if i = start then
rhs[i] = 1
elseif i = end then
rhs[i] = -1
else
rhs[i] = 0
endif
)
/\ % assert that all x values is >= 0
forall(i in 1..n, j in 1..n where d[i,j] < M) (
x[i,j] >= 0 /\ y[i,j] >= 0
)
/\ % calculate out flow
forall(i in 1..n) (
outFlow[i] = sum(j in 1..n where d[i,j] < M) (x[i,j])
)
/\ % calculate in flow
forall(j in 1..n) (
inFlow[j] = sum(i in 1..n where d[i,j] < M) (x[i,j])
)
/\ % outflow = inflow
forall(i in 1..n) (outFlow[i] - inFlow[i] = rhs[i])
/\ % do not loops
forall(i in 1..n) (
x[i,i] = 0
)
/\ % sanity: there can be no connection in x if there is not
% connection in d
forall(i,j in 1..n) (
if d[i,j] = M then
x[i,j] = 0
else
true
endif
)
;
solve minimize total_cost;
output [
if i = 1 /\ j = 1 then
"total_cost: " ++ show(total_cost) ++ "\n" ++
"inFlow: " ++ show(inFlow) ++ "\n" ++ "outFlow: " ++ show(outFlow) ++ "\n" ++
" 1 2 3 4 5 6 7 8\n"
else "" endif ++
if j = 1 then show(i) ++ " : " else "" endif ++
show_int(4,x[i,j]) ++ if j = n then "\n" else " " endif
| i in 1..n, j in 1..n
];
The solution gives an output matrix that indicates which edge of a graph is participating in the solution; however, the solution is directionless. I cannot tell the order of edge to take on a particular solution. In the above example, the shortest path from node 2 to node 1 gives the following solution
total_cost: 6
inFlow: [1, 0, 0, 0, 1, 0, 0, 1]
outFlow: [0, 1, 0, 0, 1, 0, 0, 1]
1 2 3 4 5 6 7 8
1 : 0 0 0 0 0 0 0 0
2 : 0 0 0 0 1 0 0 0
3 : 0 0 0 0 0 0 0 0
4 : 0 0 0 0 0 0 0 0
5 : 0 0 0 0 0 0 0 1
6 : 0 0 0 0 0 0 0 0
7 : 0 0 0 0 0 0 0 0
8 : 1 0 0 0 0 0 0 0
which suggests to the edge 8->1, 2->5, 5->8 are taken but I won't be able to order all edges as 2->5, 5->8, and 8->1.
I was thinking to find the index at where the start node is (here it is 2,5) and search the matrix until x[i,j]>0 and x[j,k]>0 where inFlow[j]=outFlow[j]=1, but it does not work since there may have more than one k satisfying the problem (the output graph is directionless). I wonder if there is any idea how to save the order of edges in solution. Thanks.
One way would be over a variable representing the path:
array[1..n] of var 0..n: path;
Define the path through constraints:
constraint
% start point
path[1] = start
/\ % end point
path[sum(inFlow) + 1] = end
/\ % interior points
forall(p in 2..sum(inFlow))
(path[p] = sum(i in 1..n)(i * x[path[p-1], i]));
Then show the path as part of the output statement:
"path: " ++ show([path[i] | i in 1..sum(inFlow) + 1]) ++ "\n" ++