MATP6620 / DSES6760
Combinatorial Optimization and Integer Programming

Finding violated odd-subset constraints for MAXCUT
John Mitchell

The MAXCUT problem can be formulated using variables

\begin{displaymath}
x_e = \left\{ \begin{array}{ll}
1 & \mbox{if $e$\space is in the cut} \\
0 & \mbox{otherwise}
\end{array} \right.
\end{displaymath}

One class of constraints for this problem is the set of odd subset constraints:

 \begin{displaymath}
\sum_{e \in F} x_e - \sum_{e \in C \setminus F} x_e
\leq \vert F\vert - 1
\end{displaymath} (1)

where C is a chordless cycle in the graph and $F \subseteq C$ with |F| odd. This document describes the Barahona-Mahjoub [1] routine for finding violated constraints of this form.

A solution x for the current relaxation of the maxcut problem is known. These are regarded as the edge weights. The routine duplicates the original graph, along with these weights. Thus, each edge i now has a copy i'. If (i,j) is an edge in the original graph, then edges are introduced between vertices i and j' and between i' and j with weights 1-xij. For each vertex i, the algorithm looks for a shortest path between vertex i and vertex i'. Any such path of length smaller than one can be converted into a violated constraint of the form (1). In particular, the edges of the path are the edges of the cycle in the original graph, and the subset F consists of the edges in the path with one endpoint in the original nodes and one endpoint in the duplicated set of nodes.

For example, consider the graph with xe shown:


\begin{picture}
(300,200)(20,0)
\put(50,50){\circle*{5}}
\put(55,40){$v_7$ }
...
...15){0.1}
\put(155,120){0.3}
\put(200,140){1}
\put(255,125){0.9}
\end{picture}

This graph is duplicated and connecting edges are added. In the picture, we just indicate three of the edges between the original graph and its copy. The number of such edges is actually twice the number of edges in the original graph.


\begin{picture}
(300,350)(20,0)
%original graph
\put(50,50){\circle*{5}}
\put(5...
...200,170){0.2}
\par
\put(150,150){\line(1,3){50}}
\put(160,170){0}
\end{picture}

This graph contains a path of length 0.7 from vertex v1 to vertex v1', as shown in the next picture. Since the path length is smaller than 1.0, we have a violated constraint.


\begin{picture}
(300,350)(20,0)
%original graph
\put(50,50){\circle*{5}}
\put(5...
...200,170){0.2}
\par
\put(150,150){\line(1,3){50}}
\put(160,170){0}
\end{picture}

The cycle C is thus {v1,v6,v2,v7,v3,v4,v1} and the edges in the set F are (v1,v6), (v2,v6) and (v1,v4). The size of F is three, but the current value of

\begin{displaymath}
\sum_{e \in F} x_e - \sum_{e \in C \setminus F} x_e
\end{displaymath}

is 0.9+0.8+1-0.1-0.1-0.2=2.3>|F|-1.

Notice that the violation of the constraint is 0.3. This is exactly the shortfall between the path length 0.7 and the threshold value 1.0. Stated differently, the violation of the constraint and the path length add up to one.

Exercise: Show that the sum of the violation of the constraint and the path length is always equal to one.

It follows that if there are any violated constraints then the corresponding path will have length smaller than one, so searching for the shortest path will lead to the violated constraint.

Heuristics:

The Barahona-Mahjoub routine is expensive, so heuristics are often used to find violated constraints. (See [2], for example.) One heuristic is a breadth-first search: starting at a vertex, grow a tree through the graph only using edges with xe close to zero or one. If the branches of the tree meet, a cycle has been formed. If there is an odd number of edges on this cycle with xe close to one then we have a candidate for violation of (1).

Say in the graph above, we put an edge in the tree if $x_e \leq 0.2$ or $x_e \geq 0.8$. Then this will give edges around the outside of the graph, together with the edge (v3,v5).

In particular, starting from v1 with an empty tree, we first add edges (v1,v4) and (v1,v6) to the tree. Growing from v4 adds the edge (v4,v3). Growing from v6 adds the edge (v2,v6). Growing from v3 adds the edges (v3,v5) and (v3,v7). This gives the following tree:


\begin{picture}
(300,200)(20,0)
\put(50,50){\circle*{5}}
\put(55,40){$v_7$ }
...
...90){0.1}
\put(100,115){0.1}
\put(200,140){1}
\put(255,125){0.9}
\end{picture}

Now growing the tree from vertex v2 leads to the addition of edge (v2,v7), which creates the cycle we saw before.

This heuristic is a lot quicker than the Barahona-Mahjoub algorithm. However, it may miss a constraint. For example, if we change the thresholds from 0.2 and 0.8 to 0.1 and 0.9 then we would not have found the cycle; if we make the thresholds too large, then the tree becomes too dense and there is an excess of choice, which makes it hard to identify the violated constraint.



 
John E Mitchell
2003-03-03