lemon-project-template-glpk
comparison 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 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:faed95d8083f |
---|---|
1 /* SPP, Shortest Path Problem */ | |
2 | |
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ | |
4 | |
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. */ | |
8 | |
9 param n, integer, > 0; | |
10 /* number of nodes */ | |
11 | |
12 set E, within {i in 1..n, j in 1..n}; | |
13 /* set of edges */ | |
14 | |
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) */ | |
18 | |
19 param s, in {1..n}; | |
20 /* source node */ | |
21 | |
22 param t, in {1..n}; | |
23 /* target node */ | |
24 | |
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 */ | |
30 | |
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 */ | |
35 | |
36 minimize Z: sum{(i,j) in E} c[i,j] * x[i,j]; | |
37 /* objective function is the path length to be minimized */ | |
38 | |
39 data; | |
40 | |
41 /* Optimal solution is 20 that corresponds to the following shortest | |
42 path: s = 1 -> 2 -> 4 -> 8 -> 6 = t */ | |
43 | |
44 param n := 8; | |
45 | |
46 param s := 1; | |
47 | |
48 param t := 6; | |
49 | |
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; | |
66 | |
67 end; |