COIN-OR::LEMON - Graph Library

source: glpk-cmake/examples/maxcut.mod

Last change on this file was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 14 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 2.7 KB
Line 
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
15set E, dimen 2;
16/* set of edges */
17
18param w{(i,j) in E}, >= 0, default 1;
19/* w[i,j] is weight of edge (i,j) */
20
21set V := (setof{(i,j) in E} i) union (setof{(i,j) in E} j);
22/* set of nodes */
23
24var 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
66var t{(i,j) in E}, binary;
67/* t[i,j] = x[i] and x[j] = (x[i] + x[j]) div 2 */
68
69s.t. xor{(i,j) in E}: 0 <= x[i] + x[j] - 2 * t[i,j] <= 1;
70/* see (4) */
71
72maximize z: sum{(i,j) in E} w[i,j] * (x[i] + x[j] - 2 * t[i,j]);
73/* see (6) */
74
75data;
76
77/* In this example the network has 15 nodes and 22 edges. */
78
79/* Optimal solution is 20 */
80
81set 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
85end;
Note: See TracBrowser for help on using the repository browser.