# source:glpk-cmake/examples/mfvsp.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.9 KB
Line
1/* MFVSP, Minimum Feedback Vertex Set Problem */
2
3/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
4
5/* The Minimum Feedback Vertex Set Problem for a given directed graph
6   G = (V, E), where V is a set of vertices and E is a set of arcs, is
7   to find a minimal subset of vertices, which being removed from the
8   graph make it acyclic.
9
10   Reference:
11   Garey, M.R., and Johnson, D.S. (1979), Computers and Intractability:
12   A guide to the theory of NP-completeness [Graph Theory, Covering and
13   Partitioning, Minimum Feedback Vertex Set, GT8]. */
14
15param n, integer, >= 0;
16/* number of vertices */
17
18set V, default 1..n;
19/* set of vertices */
20
21set E, within V cross V,
22default setof{i in V, j in V: i <> j and Uniform(0,1) <= 0.15} (i,j);
23/* set of arcs */
24
25printf "Graph has %d vertices and %d arcs\n", card(V), card(E);
26
27var x{i in V}, binary;
28/* x[i] = 1 means that i is a feedback vertex */
29
30/* It is known that a digraph G = (V, E) is acyclic if and only if its
31   vertices can be assigned numbers from 1 to |V| in such a way that
32   k[i] + 1 <= k[j] for every arc (i->j) in E, where k[i] is a number
33   assigned to vertex i. We may use this condition to require that the
34   digraph G = (V, E \ E'), where E' is a subset of feedback arcs, is
35   acyclic. */
36
37var k{i in V}, >= 1, <= card(V);
38/* k[i] is a number assigned to vertex i */
39
40s.t. r{(i,j) in E}: k[j] - k[i] >= 1 - card(V) * (x[i] + x[j]);
41/* note that x[i] = 1 or x[j] = 1 leads to a redundant constraint */
42
43minimize obj: sum{i in V} x[i];
44/* the objective is to minimize the cardinality of a subset of feedback
45   vertices */
46
47solve;
48
49printf "Minimum feedback vertex set:\n";
50printf{i in V: x[i]} "%d\n", i;
51
52data;
53
54/* The optimal solution is 3 */
55
56param n := 15;
57
58set 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,
59         10 11, 10 14, 11 15, 12 7, 12 8, 12 13, 13 8, 13 12, 13 14,
60         14 9, 15 14;
61
62end;
Note: See TracBrowser for help on using the repository browser.