1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/examples/mfasp.mod	Mon Dec 06 13:09:21 2010 +0100
     1.3 @@ -0,0 +1,62 @@
     1.4 +/* MFASP, Minimum Feedback Arc Set Problem */
     1.5 +
     1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
     1.7 +
     1.8 +/* The Minimum Feedback Arc Set Problem for a given directed graph
     1.9 +   G = (V, E), where V is a set of vertices and E is a set of arcs, is
    1.10 +   to find a minimal subset of arcs, which being removed from the graph
    1.11 +   make it acyclic.
    1.12 +
    1.13 +   Reference:
    1.14 +   Garey, M.R., and Johnson, D.S. (1979), Computers and Intractability:
    1.15 +   A guide to the theory of NP-completeness [Graph Theory, Covering and
    1.16 +   Partitioning, Minimum Feedback Arc Set, GT9]. */
    1.17 +
    1.18 +param n, integer, >= 0;
    1.19 +/* number of vertices */
    1.20 +
    1.21 +set V, default 1..n;
    1.22 +/* set of vertices */
    1.23 +
    1.24 +set E, within V cross V,
    1.25 +default setof{i in V, j in V: i <> j and Uniform(0,1) <= 0.15} (i,j);
    1.26 +/* set of arcs */
    1.27 +
    1.28 +printf "Graph has %d vertices and %d arcs\n", card(V), card(E);
    1.29 +
    1.30 +var x{(i,j) in E}, binary;
    1.31 +/* x[i,j] = 1 means that (i->j) is a feedback arc */
    1.32 +
    1.33 +/* It is known that a digraph G = (V, E) is acyclic if and only if its
    1.34 +   vertices can be assigned numbers from 1 to |V| in such a way that
    1.35 +   k[i] + 1 <= k[j] for every arc (i->j) in E, where k[i] is a number
    1.36 +   assigned to vertex i. We may use this condition to require that the
    1.37 +   digraph G = (V, E \ E'), where E' is a subset of feedback arcs, is
    1.38 +   acyclic. */
    1.39 +
    1.40 +var k{i in V}, >= 1, <= card(V);
    1.41 +/* k[i] is a number assigned to vertex i */
    1.42 +
    1.43 +s.t. r{(i,j) in E}: k[j] - k[i] >= 1 - card(V) * x[i,j];
    1.44 +/* note that x[i,j] = 1 leads to a redundant constraint */
    1.45 +
    1.46 +minimize obj: sum{(i,j) in E} x[i,j];
    1.47 +/* the objective is to minimize the cardinality of a subset of feedback
    1.48 +   arcs */
    1.49 +
    1.50 +solve;
    1.51 +
    1.52 +printf "Minimum feedback arc set:\n";
    1.53 +printf{(i,j) in E: x[i,j]} "%d %d\n", i, j;
    1.54 +
    1.55 +data;
    1.56 +
    1.57 +/* The optimal solution is 3 */
    1.58 +
    1.59 +param n := 15;
    1.60 +
    1.61 +set E := 1 2, 2 3, 3 4, 3 8, 4 9, 5 1, 6 5, 7 5, 8 6, 8 7, 8 9, 9 10,
    1.62 +         10 11, 10 14, 11 15, 12 7, 12 8, 12 13, 13 8, 13 12, 13 14,
    1.63 +         14 9, 15 14;
    1.64 +
    1.65 +end;