Valid inequalities for max-cut

From cophywiki
Jump to: navigation, search


In this article we explain relevant concepts for understanding the geometry of the cut polytope. The latter is important for the development of an effective branch-and-cut algorithm for determining optimum solutions for max-cut and for exact ground states of Ising spin glasses, cf. the article about computing exact ground states of Ising spin glasses.

Valid inequalities for max-cut

Next we introduce classes of inequalities that are valid or facet defining for the cut polytope. Optimizing over the corresponding relaxations yields bounds that can be used within a branch-and-cut procedure. Given a graph G = (V,E), an incidence vector \chi of a cut obviously has to satisfy

0\ \le\ x_e\ \le\ 1\ \forall\ e\ \in\ E\,\!

Barahona and Mahjoub proved that these 'trivial' inequalities define a facet of the cut polytope P_C(G) if and only if e does not belong to a triangle.
A class that is more interesting than the trivial inequalities are the cycle inequalities. An edge set C = \{(v_0,v_1),(v_1,v_2),...,(v_{k-1},v_0)\}\ \subseteq\ E is called a cycle (of length k) in the graph G = (V,E).

Let C\ \subseteq\ E be a cycle and e be an edge that does not belong to C.

We say e is a chord of C if it joins two nodes of C.

A cycle C is called chordless if it does not contain a chord.

The cycle inequalities are drawn from the observation that a cut and a cycle can only have an even number of common edges.
Let C\ \subseteq\ E be a cycle in G = (V,E) and F\ \subseteq\ C a subset of cycle edges of odd cardinality. Then the cycle inequality

\sum\limits_{e\ \in\ F} x_e - \sum\limits_{e\ in\ C\setminus F} x_e\ \le\ |F| - 1

is valid for the cut polytope P_C(G). Barahona and Mahjoub proved that the cycle inequalities are facets in case C is chordless.
The triangle inequalities

x_{ij} &+& x_{ik} &+& x_{jk} & \le\ & 2 \\
x_{ij} &-& x_{ik} &-& x_{jk} & \le\ & 0 \\
-x_{ij} &+& x_{ik} &-& x_{jk} & \le\ & 0 \\
-x_{ij} &-& x_{ik} &+& x_{jk} & \le\ & 0

for triangle i,\ j,\ k in G are a special case of the cycle inequalities for |C| = 3 and define facets of P_C(G).


We consider the graph consisting of a triangle.

The cycle inequalities read

x_{12} &+& x_{13} &+& x_{23} & \le\ & 2 \\
x_{12} &-& x_{13} &-& x_{23} & \le\ & 0 \\
-x_{12} &+& x_{13} &-& x_{23} & \le\ & 0 \\
-x_{12} &-& x_{13} &+& x_{23} & \le\ & 0

Indeed, for the four incidence vectors of cuts shown in the example these inequalities are satisfied. Furthermore, zero - one vectors that do not correspond to cuts violate the cycle inequalities. For example the vector \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} which does not define a cut does not satisfy the first triangle inequality.

The cycle polytope of K_p, where K_p is the complete graph on p nodes, consists of all 4 \begin{pmatrix}p \\ 3 \end{pmatrix} triangle inequalities.

Separation of the cycle inequalities

For making use of the cycle inequalities within branch-and-cut we have to solve the separation problem for the cycle inequalities. We formulate it as follows.
Given x^*\ \in\ \mathbb{R}^m with 0\ \le\ x_e^*\ \le\ 1 for all edges e in E, decide wether x^* satisfies all cycle inequalities. If not, return a cycle inequality

\sum\limits_{e\ \in\ F} x_e - \sum\limits_{e\ \in\ C\setminus F} x_e\ \le\ |F| - 1

violated by x^*.
Barahona and Mahjoub also proved that this separation problem can be solved in polynomial time for cycle inequalities.