lemon-project-template-glpk
comparison deps/glpk/examples/mvcp.mod @ 9:33de93886c88
Import GLPK 4.47
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 20:59:10 +0100 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:2a7b26e07232 |
---|---|
1 /* MVCP, Minimum Vertex Cover Problem */ | |
2 | |
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ | |
4 | |
5 /* The Minimum Vertex Cover Problem in a network G = (V, E), where V | |
6 is a set of nodes, E is a set of arcs, is to find a subset V' within | |
7 V such that each edge (i,j) in E has at least one its endpoint in V' | |
8 and which minimizes the sum of node weights w(i) over V'. | |
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 Vertex Cover, GT1]. */ | |
14 | |
15 set E, dimen 2; | |
16 /* set of edges */ | |
17 | |
18 set V := (setof{(i,j) in E} i) union (setof{(i,j) in E} j); | |
19 /* set of nodes */ | |
20 | |
21 param w{i in V}, >= 0, default 1; | |
22 /* w[i] is weight of vertex i */ | |
23 | |
24 var x{i in V}, binary; | |
25 /* x[i] = 1 means that node i is included into V' */ | |
26 | |
27 s.t. cov{(i,j) in E}: x[i] + x[j] >= 1; | |
28 /* each edge (i,j) must have node i or j (or both) in V' */ | |
29 | |
30 minimize z: sum{i in V} w[i] * x[i]; | |
31 /* we need to minimize the sum of node weights over V' */ | |
32 | |
33 data; | |
34 | |
35 /* These data correspond to an example from [Papadimitriou]. */ | |
36 | |
37 /* Optimal solution is 6 (greedy heuristic gives 13) */ | |
38 | |
39 set E := a1 b1, b1 c1, a1 b2, b2 c2, a2 b3, b3 c3, a2 b4, b4 c4, a3 b5, | |
40 b5 c5, a3 b6, b6 c6, a4 b1, a4 b2, a4 b3, a5 b4, a5 b5, a5 b6, | |
41 a6 b1, a6 b2, a6 b3, a6 b4, a7 b2, a7 b3, a7 b4, a7 b5, a7 b6; | |
42 | |
43 end; |