Max-Cut

The Max-Cut problem is one of the best know and most studied problems of Combinatorial Optimization. It can be described as follows.

A weighted undirected graph G = (V, E, w) is given, where V is a set of nodes and E is a set of edges, i.e., of unordered pairs of nodes. An edge of E is denoted 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 is assigned a weight, i.e., a real number wij.

For any partition (W, V\W) of the node-set V, let us consider the edges of E having the two end-nodes in different sets of the partition. This subset of edges is called a cut. Therefore, we have a cut for every partition of V.  If W is empty or if W=V, the partition is made of a single set and the corresponding cut is the empty set. If V has n nodes, the total number of partitions (including the degenerate partition with a single set) is 2n-1, thus 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.

Why Max-Cut is a logoptimization problem?

If we assign a binary variable xi 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 xi and xj differ. Therefore, we would need a function of xi and xj 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-xi) xj + xi (1 – xj). Then the weight of the cut can be expressed as the following polynomial of degree 2 in the variables xi with i ∈ V:

Σ { wij ( (1-xi)xj + (1-xj)xi ), ij E  },

where Σ {wij ((1 – xi) xj + (1 – xj) xi), ij ∈ E} denotes the sum of the monomials wij ((1 – xi) xj + (1 – xj) xi) for all edges ij of G. Maximizing such a function is, evidently, a logoptimization problem.

SovingMax-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, techniques have been developed to provide good solutions to the problem along with a quality certificate.

A quality certificate is provided 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 has been computed, it is possible to evaluate the quality of a given cut by computing the gap between the bound and the cut weight. A simple upper bound can be computed by adding up the absolute value of the weights of all edges of the graph. However, such an upper bound, that is very fast to compute, would provide, 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.

As said, fortunately, procedures have been developed 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,

were the solution of instances of sizes up to a million nodes is reported 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.