| rev |
line source |
|
alpar@9
|
1 /* MVCP, Minimum Vertex Cover Problem */
|
|
alpar@9
|
2
|
|
alpar@9
|
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
|
|
alpar@9
|
4
|
|
alpar@9
|
5 /* The Minimum Vertex Cover Problem in a network G = (V, E), where V
|
|
alpar@9
|
6 is a set of nodes, E is a set of arcs, is to find a subset V' within
|
|
alpar@9
|
7 V such that each edge (i,j) in E has at least one its endpoint in V'
|
|
alpar@9
|
8 and which minimizes the sum of node weights w(i) over V'.
|
|
alpar@9
|
9
|
|
alpar@9
|
10 Reference:
|
|
alpar@9
|
11 Garey, M.R., and Johnson, D.S. (1979), Computers and Intractability:
|
|
alpar@9
|
12 A guide to the theory of NP-completeness [Graph Theory, Covering and
|
|
alpar@9
|
13 Partitioning, Minimum Vertex Cover, GT1]. */
|
|
alpar@9
|
14
|
|
alpar@9
|
15 set E, dimen 2;
|
|
alpar@9
|
16 /* set of edges */
|
|
alpar@9
|
17
|
|
alpar@9
|
18 set V := (setof{(i,j) in E} i) union (setof{(i,j) in E} j);
|
|
alpar@9
|
19 /* set of nodes */
|
|
alpar@9
|
20
|
|
alpar@9
|
21 param w{i in V}, >= 0, default 1;
|
|
alpar@9
|
22 /* w[i] is weight of vertex i */
|
|
alpar@9
|
23
|
|
alpar@9
|
24 var x{i in V}, binary;
|
|
alpar@9
|
25 /* x[i] = 1 means that node i is included into V' */
|
|
alpar@9
|
26
|
|
alpar@9
|
27 s.t. cov{(i,j) in E}: x[i] + x[j] >= 1;
|
|
alpar@9
|
28 /* each edge (i,j) must have node i or j (or both) in V' */
|
|
alpar@9
|
29
|
|
alpar@9
|
30 minimize z: sum{i in V} w[i] * x[i];
|
|
alpar@9
|
31 /* we need to minimize the sum of node weights over V' */
|
|
alpar@9
|
32
|
|
alpar@9
|
33 data;
|
|
alpar@9
|
34
|
|
alpar@9
|
35 /* These data correspond to an example from [Papadimitriou]. */
|
|
alpar@9
|
36
|
|
alpar@9
|
37 /* Optimal solution is 6 (greedy heuristic gives 13) */
|
|
alpar@9
|
38
|
|
alpar@9
|
39 set E := a1 b1, b1 c1, a1 b2, b2 c2, a2 b3, b3 c3, a2 b4, b4 c4, a3 b5,
|
|
alpar@9
|
40 b5 c5, a3 b6, b6 c6, a4 b1, a4 b2, a4 b3, a5 b4, a5 b5, a5 b6,
|
|
alpar@9
|
41 a6 b1, a6 b2, a6 b3, a6 b4, a7 b2, a7 b3, a7 b4, a7 b5, a7 b6;
|
|
alpar@9
|
42
|
|
alpar@9
|
43 end;
|
