Max-Cut

Max-Cut is the problem of finding cuts of maximum weight in graphs. It is one of the best know and most studied problems of Combinatorial Optimization. Its descriptions is as follows.

Our data is a weighted undirected graph  G=(V, E, w), where V is a set of nodes and E is a set of edges, i.e., of unordered pairs of nodes. We denote an edge of E by the two nodes of the corresponding pair, thus, e.g., ij is the edge having i and j as end-nodes. Every edge ij of E has a weight, i.e., a real number w_{ij}.

For any partition (W, V\setminus W) of the node-set V, we pick the edges of G having the two end-nodes in different sets of the partition. We call such a subset of edges a cut. Therefore, we have a cut for every partition of V.  If W is empty or if W=V, one of the two sets of the partition is empty, thus the corresponding cut has no edges. If V has n nodes, the total number of partitions (including the degenerate partition with a single non-empty set) is 2^{n-1} therefore, these many are the different cuts of G. The weight of a cut is the sum of the weights of its edges.

The Max-Cut Problem calls for a cut of maximum weight among all cuts of G. Because an empty set is a legal cut of G (whose weight is 0), the value of a maximum weight cut cannot be negative.

Why Max-Cut is a logoptimization problem?

How finding a cut of maximum weight in a graph can be seen as a logoptimization problem? If we assign a binary variable x_i to each node i of V, every assignment of the values 0 or 1 to these variables will correspond to a partition of V. An edge ij belongs to the cut associated with such a partition if and only if the values of x_i and x_j differ. Therefore, we would need a function of x_i and x_j that has value 1 when the two variables have different values and 0 otherwise.

It is easy to verify that such a function can be expressed, using elementary arithmetic operations, as (1-x_i)x_j+ x_i(1 - x_j). Then the weight of the cut can be expressed as the following polynomial of degree 2 in the variables x_i with i\in V:

    \[ \sum\left\{w_{ij}\big(x_i(1-x_j) + (1-x_i)x_j\big),\; ij\in E\right\}, \]

that is the sum of the monomials w_{ij}\big(x_i(1-x_j) + (1-x_i)x_j\big) for all edges ij of G. Maximizing such a sum is, evidently, a logoptimization problem.

Solving Max-Cut

The solution of Max-Cut to certified optimality is quite a difficult task for graphs of more than a few hundred nodes, unless the graph is very sparse. However, several techniques are available that produce good solutions to the problem along with a quality certificate.

One can generate a quality certificate by computing an upper bound to the problem, i.e., a value that is mathematically guaranteed not to be below the optimal value. Once an upper bound is at hand, it is possible to evaluate the quality of a given cut by computing the gap between the bound and its weight.

How difficult it is to find an upper bound? An easy way is to take the sum of the positive weights of all G. Certainly no cut can have a weight larger than this one. However, such an upper bound, that is very fast to compute, would generate, in general, horribly large gaps also for cuts very close to the optimum. Therefore, the challenge is to design efficient procedures that can compute upper bounds that are reasonably close to the optimal value.

SpeeDP

As said, fortunately, procedures are available that make it possible to find good cuts of very large graphs with a quality certified by a small gap. A very effective technique of this kind is based on the algorithm SpeeDP described in

L. Grippo, L. Palagi, M. Piacentini, V. Piccialli, and G. Rinaldi:
SpeeDP: An algorithm to compute SDP bounds for very large Max-Cut in­stan­ces.
Mathematical Programming 136 (2012), 353-373,

that reports the solution of instances of sizes up to a million nodes with gaps below 1%.

Our LOGOPTIMIZE server incorporates the SpeeDP algorithm and is able to handle very large instances of the problem, proving lower and upper bounds.