1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/examples/maxcut.mod	Mon Dec 06 13:09:21 2010 +0100
     1.3 @@ -0,0 +1,85 @@
     1.4 +/* MAXCUT, Maximum Cut Problem */
     1.5 +
     1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
     1.7 +
     1.8 +/* The Maximum Cut Problem in a network G = (V, E), where V is a set
     1.9 +   of nodes, E is a set of edges, is to find the partition of V into
    1.10 +   disjoint sets V1 and V2, which maximizes the sum of edge weights
    1.11 +   w(e), where edge e has one endpoint in V1 and other endpoint in V2.
    1.12 +
    1.13 +   Reference:
    1.14 +   Garey, M.R., and Johnson, D.S. (1979), Computers and Intractability:
    1.15 +   A guide to the theory of NP-completeness [Network design, Cuts and
    1.16 +   Connectivity, Maximum Cut, ND16]. */
    1.17 +
    1.18 +set E, dimen 2;
    1.19 +/* set of edges */
    1.20 +
    1.21 +param w{(i,j) in E}, >= 0, default 1;
    1.22 +/* w[i,j] is weight of edge (i,j) */
    1.23 +
    1.24 +set V := (setof{(i,j) in E} i) union (setof{(i,j) in E} j);
    1.25 +/* set of nodes */
    1.26 +
    1.27 +var x{i in V}, binary;
    1.28 +/* x[i] = 0 means that node i is in set V1
    1.29 +   x[i] = 1 means that node i is in set V2 */
    1.30 +
    1.31 +/* We need to include in the objective function only that edges (i,j)
    1.32 +   from E, for which x[i] != x[j]. This can be modeled through binary
    1.33 +   variables s[i,j] as follows:
    1.34 +
    1.35 +      s[i,j] = x[i] xor x[j] = (x[i] + x[j]) mod 2,                  (1)
    1.36 +
    1.37 +   where s[i,j] = 1 iff x[i] != x[j], that leads to the following
    1.38 +   objective function:
    1.39 +
    1.40 +      z = sum{(i,j) in E} w[i,j] * s[i,j].                           (2)
    1.41 +
    1.42 +   To describe "exclusive or" (1) we could think that s[i,j] is a minor
    1.43 +   bit of the sum x[i] + x[j]. Then introducing binary variables t[i,j],
    1.44 +   which represent a major bit of the sum x[i] + x[j], we can write:
    1.45 +
    1.46 +      x[i] + x[j] = s[i,j] + 2 * t[i,j].                             (3)
    1.47 +
    1.48 +   An easy check shows that conditions (1) and (3) are equivalent.
    1.49 +
    1.50 +   Note that condition (3) can be simplified by eliminating variables
    1.51 +   s[i,j]. Indeed, from (3) it follows that:
    1.52 +
    1.53 +      s[i,j] = x[i] + x[j] - 2 * t[i,j].                             (4)
    1.54 +
    1.55 +   Since the expression in the right-hand side of (4) is integral, this
    1.56 +   condition can be rewritten in the equivalent form:
    1.57 +
    1.58 +      0 <= x[i] + x[j] - 2 * t[i,j] <= 1.                            (5)
    1.59 +
    1.60 +   (One might note that (5) means t[i,j] = x[i] and x[j].)
    1.61 +
    1.62 +   Substituting s[i,j] from (4) to (2) leads to the following objective
    1.63 +   function:
    1.64 +
    1.65 +      z = sum{(i,j) in E} w[i,j] * (x[i] + x[j] - 2 * t[i,j]),       (6)
    1.66 +
    1.67 +   which does not include variables s[i,j]. */
    1.68 +
    1.69 +var t{(i,j) in E}, binary;
    1.70 +/* t[i,j] = x[i] and x[j] = (x[i] + x[j]) div 2 */
    1.71 +
    1.72 +s.t. xor{(i,j) in E}: 0 <= x[i] + x[j] - 2 * t[i,j] <= 1;
    1.73 +/* see (4) */
    1.74 +
    1.75 +maximize z: sum{(i,j) in E} w[i,j] * (x[i] + x[j] - 2 * t[i,j]);
    1.76 +/* see (6) */
    1.77 +
    1.78 +data;
    1.79 +
    1.80 +/* In this example the network has 15 nodes and 22 edges. */
    1.81 +
    1.82 +/* Optimal solution is 20 */
    1.83 +
    1.84 +set E :=
    1.85 +   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,
    1.86 +   8 12, 9 10, 9 14, 10 11, 10 14, 11 15, 12 13, 13 14, 14 15;
    1.87 +
    1.88 +end;