| rev |
line source |
|
alpar@9
|
1 /* MAXCUT, Maximum Cut Problem */
|
|
alpar@9
|
2
|
|
alpar@9
|
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
|
|
alpar@9
|
4
|
|
alpar@9
|
5 /* The Maximum Cut Problem in a network G = (V, E), where V is a set
|
|
alpar@9
|
6 of nodes, E is a set of edges, is to find the partition of V into
|
|
alpar@9
|
7 disjoint sets V1 and V2, which maximizes the sum of edge weights
|
|
alpar@9
|
8 w(e), where edge e has one endpoint in V1 and other endpoint in V2.
|
|
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 [Network design, Cuts and
|
|
alpar@9
|
13 Connectivity, Maximum Cut, ND16]. */
|
|
alpar@9
|
14
|
|
alpar@9
|
15 set E, dimen 2;
|
|
alpar@9
|
16 /* set of edges */
|
|
alpar@9
|
17
|
|
alpar@9
|
18 param w{(i,j) in E}, >= 0, default 1;
|
|
alpar@9
|
19 /* w[i,j] is weight of edge (i,j) */
|
|
alpar@9
|
20
|
|
alpar@9
|
21 set V := (setof{(i,j) in E} i) union (setof{(i,j) in E} j);
|
|
alpar@9
|
22 /* set of nodes */
|
|
alpar@9
|
23
|
|
alpar@9
|
24 var x{i in V}, binary;
|
|
alpar@9
|
25 /* x[i] = 0 means that node i is in set V1
|
|
alpar@9
|
26 x[i] = 1 means that node i is in set V2 */
|
|
alpar@9
|
27
|
|
alpar@9
|
28 /* We need to include in the objective function only that edges (i,j)
|
|
alpar@9
|
29 from E, for which x[i] != x[j]. This can be modeled through binary
|
|
alpar@9
|
30 variables s[i,j] as follows:
|
|
alpar@9
|
31
|
|
alpar@9
|
32 s[i,j] = x[i] xor x[j] = (x[i] + x[j]) mod 2, (1)
|
|
alpar@9
|
33
|
|
alpar@9
|
34 where s[i,j] = 1 iff x[i] != x[j], that leads to the following
|
|
alpar@9
|
35 objective function:
|
|
alpar@9
|
36
|
|
alpar@9
|
37 z = sum{(i,j) in E} w[i,j] * s[i,j]. (2)
|
|
alpar@9
|
38
|
|
alpar@9
|
39 To describe "exclusive or" (1) we could think that s[i,j] is a minor
|
|
alpar@9
|
40 bit of the sum x[i] + x[j]. Then introducing binary variables t[i,j],
|
|
alpar@9
|
41 which represent a major bit of the sum x[i] + x[j], we can write:
|
|
alpar@9
|
42
|
|
alpar@9
|
43 x[i] + x[j] = s[i,j] + 2 * t[i,j]. (3)
|
|
alpar@9
|
44
|
|
alpar@9
|
45 An easy check shows that conditions (1) and (3) are equivalent.
|
|
alpar@9
|
46
|
|
alpar@9
|
47 Note that condition (3) can be simplified by eliminating variables
|
|
alpar@9
|
48 s[i,j]. Indeed, from (3) it follows that:
|
|
alpar@9
|
49
|
|
alpar@9
|
50 s[i,j] = x[i] + x[j] - 2 * t[i,j]. (4)
|
|
alpar@9
|
51
|
|
alpar@9
|
52 Since the expression in the right-hand side of (4) is integral, this
|
|
alpar@9
|
53 condition can be rewritten in the equivalent form:
|
|
alpar@9
|
54
|
|
alpar@9
|
55 0 <= x[i] + x[j] - 2 * t[i,j] <= 1. (5)
|
|
alpar@9
|
56
|
|
alpar@9
|
57 (One might note that (5) means t[i,j] = x[i] and x[j].)
|
|
alpar@9
|
58
|
|
alpar@9
|
59 Substituting s[i,j] from (4) to (2) leads to the following objective
|
|
alpar@9
|
60 function:
|
|
alpar@9
|
61
|
|
alpar@9
|
62 z = sum{(i,j) in E} w[i,j] * (x[i] + x[j] - 2 * t[i,j]), (6)
|
|
alpar@9
|
63
|
|
alpar@9
|
64 which does not include variables s[i,j]. */
|
|
alpar@9
|
65
|
|
alpar@9
|
66 var t{(i,j) in E}, binary;
|
|
alpar@9
|
67 /* t[i,j] = x[i] and x[j] = (x[i] + x[j]) div 2 */
|
|
alpar@9
|
68
|
|
alpar@9
|
69 s.t. xor{(i,j) in E}: 0 <= x[i] + x[j] - 2 * t[i,j] <= 1;
|
|
alpar@9
|
70 /* see (4) */
|
|
alpar@9
|
71
|
|
alpar@9
|
72 maximize z: sum{(i,j) in E} w[i,j] * (x[i] + x[j] - 2 * t[i,j]);
|
|
alpar@9
|
73 /* see (6) */
|
|
alpar@9
|
74
|
|
alpar@9
|
75 data;
|
|
alpar@9
|
76
|
|
alpar@9
|
77 /* In this example the network has 15 nodes and 22 edges. */
|
|
alpar@9
|
78
|
|
alpar@9
|
79 /* Optimal solution is 20 */
|
|
alpar@9
|
80
|
|
alpar@9
|
81 set E :=
|
|
alpar@9
|
82 1 2, 1 5, 2 3, 2 6, 3 4, 3 8, 4 9, 5 6, 5 7, 6 8, 7 8, 7 12, 8 9,
|
|
alpar@9
|
83 8 12, 9 10, 9 14, 10 11, 10 14, 11 15, 12 13, 13 14, 14 15;
|
|
alpar@9
|
84
|
|
alpar@9
|
85 end;
|
