alpar@1: /* MFASP, Minimum Feedback Arc Set Problem */
alpar@1: 
alpar@1: /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
alpar@1: 
alpar@1: /* The Minimum Feedback Arc Set Problem for a given directed graph
alpar@1:    G = (V, E), where V is a set of vertices and E is a set of arcs, is
alpar@1:    to find a minimal subset of arcs, which being removed from the graph
alpar@1:    make it acyclic.
alpar@1: 
alpar@1:    Reference:
alpar@1:    Garey, M.R., and Johnson, D.S. (1979), Computers and Intractability:
alpar@1:    A guide to the theory of NP-completeness [Graph Theory, Covering and
alpar@1:    Partitioning, Minimum Feedback Arc Set, GT9]. */
alpar@1: 
alpar@1: param n, integer, >= 0;
alpar@1: /* number of vertices */
alpar@1: 
alpar@1: set V, default 1..n;
alpar@1: /* set of vertices */
alpar@1: 
alpar@1: set E, within V cross V,
alpar@1: default setof{i in V, j in V: i <> j and Uniform(0,1) <= 0.15} (i,j);
alpar@1: /* set of arcs */
alpar@1: 
alpar@1: printf "Graph has %d vertices and %d arcs\n", card(V), card(E);
alpar@1: 
alpar@1: var x{(i,j) in E}, binary;
alpar@1: /* x[i,j] = 1 means that (i->j) is a feedback arc */
alpar@1: 
alpar@1: /* It is known that a digraph G = (V, E) is acyclic if and only if its
alpar@1:    vertices can be assigned numbers from 1 to |V| in such a way that
alpar@1:    k[i] + 1 <= k[j] for every arc (i->j) in E, where k[i] is a number
alpar@1:    assigned to vertex i. We may use this condition to require that the
alpar@1:    digraph G = (V, E \ E'), where E' is a subset of feedback arcs, is
alpar@1:    acyclic. */
alpar@1: 
alpar@1: var k{i in V}, >= 1, <= card(V);
alpar@1: /* k[i] is a number assigned to vertex i */
alpar@1: 
alpar@1: s.t. r{(i,j) in E}: k[j] - k[i] >= 1 - card(V) * x[i,j];
alpar@1: /* note that x[i,j] = 1 leads to a redundant constraint */
alpar@1: 
alpar@1: minimize obj: sum{(i,j) in E} x[i,j];
alpar@1: /* the objective is to minimize the cardinality of a subset of feedback
alpar@1:    arcs */
alpar@1: 
alpar@1: solve;
alpar@1: 
alpar@1: printf "Minimum feedback arc set:\n";
alpar@1: printf{(i,j) in E: x[i,j]} "%d %d\n", i, j;
alpar@1: 
alpar@1: data;
alpar@1: 
alpar@1: /* The optimal solution is 3 */
alpar@1: 
alpar@1: param n := 15;
alpar@1: 
alpar@1: 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,
alpar@1:          10 11, 10 14, 11 15, 12 7, 12 8, 12 13, 13 8, 13 12, 13 14,
alpar@1:          14 9, 15 14;
alpar@1: 
alpar@1: end;