1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
/* SPP, Shortest Path Problem */
/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
/* Given a directed graph G = (V,E), its edge lengths c(i,j) for all
(i,j) in E, and two nodes s, t in V, the Shortest Path Problem (SPP)
is to find a directed path from s to t whose length is minimal. */
param n, integer, > 0;
/* number of nodes */
set E, within {i in 1..n, j in 1..n};
/* set of edges */
param c{(i,j) in E};
/* c[i,j] is length of edge (i,j); note that edge lengths are allowed
to be of any sign (positive, negative, or zero) */
param s, in {1..n};
/* source node */
param t, in {1..n};
/* target node */
var x{(i,j) in E}, >= 0;
/* x[i,j] = 1 means that edge (i,j) belong to shortest path;
x[i,j] = 0 means that edge (i,j) does not belong to shortest path;
note that variables x[i,j] are binary, however, there is no need to
declare them so due to the totally unimodular constraint matrix */
s.t. r{i in 1..n}: sum{(j,i) in E} x[j,i] + (if i = s then 1) =
sum{(i,j) in E} x[i,j] + (if i = t then 1);
/* conservation conditions for unity flow from s to t; every feasible
solution is a path from s to t */
minimize Z: sum{(i,j) in E} c[i,j] * x[i,j];
/* objective function is the path length to be minimized */
data;
/* Optimal solution is 20 that corresponds to the following shortest
path: s = 1 -> 2 -> 4 -> 8 -> 6 = t */
param n := 8;
param s := 1;
param t := 6;
param : E : c :=
1 2 1
1 4 8
1 7 6
2 4 2
3 2 14
3 4 10
3 5 6
3 6 19
4 5 8
4 8 13
5 8 12
6 5 7
7 4 5
8 6 4
8 7 10;
end;
|
