source:glpk-cmake/examples/mvcp.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.4 KB
Line
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
15set E, dimen 2;
16/* set of edges */
17
18set V := (setof{(i,j) in E} i) union (setof{(i,j) in E} j);
19/* set of nodes */
20
21param w{i in V}, >= 0, default 1;
22/* w[i] is weight of vertex i */
23
24var x{i in V}, binary;
25/* x[i] = 1 means that node i is included into V' */
26
27s.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
30minimize z: sum{i in V} w[i] * x[i];
31/* we need to minimize the sum of node weights over V' */
32
33data;
34
35/* These data correspond to an example from [Papadimitriou]. */
36
37/* Optimal solution is 6 (greedy heuristic gives 13) */
38
39set 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
43end;
Note: See TracBrowser for help on using the repository browser.