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