Valid inequalities for max-cut

From Cophy
Jump to: navigation, search

Contents

Introduction

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 χ 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 PC(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 = {(v0,v1),(v1,v2),...,(vk − 1,v0)} ⊆ E is called a cycle (of length k) in the graph G = (V,E).

Let C ⊆ 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 ⊆ E be a cycle in G = (V,E) and F ⊆ 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 PC(G). Barahona and Mahjoub proved that the cycle inequalities are facets in case C is chordless.
The triangle inequalities


\begin{matrix}
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
\end{matrix}

for triangle ijk in G are a special case of the cycle inequalities for | C | = 3 and define facets of PC(G).

Example

We consider the graph consisting of a triangle.

The cycle inequalities read


\begin{matrix}
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
\end{matrix}

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 Kp, where Kp 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 ≤ xe *  ≤ 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.

Personal tools