1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/examples/spp.mod	Mon Dec 06 13:09:21 2010 +0100
     1.3 @@ -0,0 +1,67 @@
     1.4 +/* SPP, Shortest Path Problem */
     1.5 +
     1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
     1.7 +
     1.8 +/* Given a directed graph G = (V,E), its edge lengths c(i,j) for all
     1.9 +   (i,j) in E, and two nodes s, t in V, the Shortest Path Problem (SPP)
    1.10 +   is to find a directed path from s to t whose length is minimal. */
    1.11 +
    1.12 +param n, integer, > 0;
    1.13 +/* number of nodes */
    1.14 +
    1.15 +set E, within {i in 1..n, j in 1..n};
    1.16 +/* set of edges */
    1.17 +
    1.18 +param c{(i,j) in E};
    1.19 +/* c[i,j] is length of edge (i,j); note that edge lengths are allowed
    1.20 +   to be of any sign (positive, negative, or zero) */
    1.21 +
    1.22 +param s, in {1..n};
    1.23 +/* source node */
    1.24 +
    1.25 +param t, in {1..n};
    1.26 +/* target node */
    1.27 +
    1.28 +var x{(i,j) in E}, >= 0;
    1.29 +/* x[i,j] = 1 means that edge (i,j) belong to shortest path;
    1.30 +   x[i,j] = 0 means that edge (i,j) does not belong to shortest path;
    1.31 +   note that variables x[i,j] are binary, however, there is no need to
    1.32 +   declare them so due to the totally unimodular constraint matrix */
    1.33 +
    1.34 +s.t. r{i in 1..n}: sum{(j,i) in E} x[j,i] + (if i = s then 1) =
    1.35 +                   sum{(i,j) in E} x[i,j] + (if i = t then 1);
    1.36 +/* conservation conditions for unity flow from s to t; every feasible
    1.37 +   solution is a path from s to t */
    1.38 +
    1.39 +minimize Z: sum{(i,j) in E} c[i,j] * x[i,j];
    1.40 +/* objective function is the path length to be minimized */
    1.41 +
    1.42 +data;
    1.43 +
    1.44 +/* Optimal solution is 20 that corresponds to the following shortest
    1.45 +   path: s = 1 -> 2 -> 4 -> 8 -> 6 = t */
    1.46 +
    1.47 +param n := 8;
    1.48 +
    1.49 +param s := 1;
    1.50 +
    1.51 +param t := 6;
    1.52 +
    1.53 +param : E :   c :=
    1.54 +       1 2    1
    1.55 +       1 4    8
    1.56 +       1 7    6
    1.57 +       2 4    2
    1.58 +       3 2   14
    1.59 +       3 4   10
    1.60 +       3 5    6
    1.61 +       3 6   19
    1.62 +       4 5    8
    1.63 +       4 8   13
    1.64 +       5 8   12
    1.65 +       6 5    7
    1.66 +       7 4    5
    1.67 +       8 6    4
    1.68 +       8 7   10;
    1.69 +
    1.70 +end;