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; |
---|