# source:glpk-cmake/examples/spp.mod@1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

• Generated files and doc/notes are removed
File size: 1.7 KB
Line
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
9param n, integer, > 0;
10/* number of nodes */
11
12set E, within {i in 1..n, j in 1..n};
13/* set of edges */
14
15param 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
19param s, in {1..n};
20/* source node */
21
22param t, in {1..n};
23/* target node */
24
25var 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
31s.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
36minimize Z: sum{(i,j) in E} c[i,j] * x[i,j];
37/* objective function is the path length to be minimized */
38
39data;
40
41/* Optimal solution is 20 that corresponds to the following shortest
42   path: s = 1 -> 2 -> 4 -> 8 -> 6 = t */
43
44param n := 8;
45
46param s := 1;
47
48param t := 6;
49
50param : 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
67end;
Note: See TracBrowser for help on using the repository browser.