1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/examples/mvcp.mod	Mon Dec 06 13:09:21 2010 +0100
     1.3 @@ -0,0 +1,43 @@
     1.4 +/* MVCP, Minimum Vertex Cover Problem */
     1.5 +
     1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
     1.7 +
     1.8 +/* The Minimum Vertex Cover Problem in a network G = (V, E), where V
     1.9 +   is a set of nodes, E is a set of arcs, is to find a subset V' within
    1.10 +   V such that each edge (i,j) in E has at least one its endpoint in V'
    1.11 +   and which minimizes the sum of node weights w(i) over V'.
    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 Vertex Cover, GT1]. */
    1.17 +
    1.18 +set E, dimen 2;
    1.19 +/* set of edges */
    1.20 +
    1.21 +set V := (setof{(i,j) in E} i) union (setof{(i,j) in E} j);
    1.22 +/* set of nodes */
    1.23 +
    1.24 +param w{i in V}, >= 0, default 1;
    1.25 +/* w[i] is weight of vertex i */
    1.26 +
    1.27 +var x{i in V}, binary;
    1.28 +/* x[i] = 1 means that node i is included into V' */
    1.29 +
    1.30 +s.t. cov{(i,j) in E}: x[i] + x[j] >= 1;
    1.31 +/* each edge (i,j) must have node i or j (or both) in V' */
    1.32 +
    1.33 +minimize z: sum{i in V} w[i] * x[i];
    1.34 +/* we need to minimize the sum of node weights over V' */
    1.35 +
    1.36 +data;
    1.37 +
    1.38 +/* These data correspond to an example from [Papadimitriou]. */
    1.39 +
    1.40 +/* Optimal solution is 6 (greedy heuristic gives 13) */
    1.41 +
    1.42 +set E := a1 b1, b1 c1, a1 b2, b2 c2, a2 b3, b3 c3, a2 b4, b4 c4, a3 b5,
    1.43 +         b5 c5, a3 b6, b6 c6, a4 b1, a4 b2, a4 b3, a5 b4, a5 b5, a5 b6,
    1.44 +         a6 b1, a6 b2, a6 b3, a6 b4, a7 b2, a7 b3, a7 b4, a7 b5, a7 b6;
    1.45 +
    1.46 +end;