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