MATP6620 / DSES6760

Combinatorial Optimization and Integer Programming

**Finding
violated odd-subset constraints for MAXCUT**

John Mitchell

Combinatorial Optimization and Integer Programming

John Mitchell

The MAXCUT problem can be formulated using variables

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

where

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-*x*_{ij}.
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 *x*_{e} shown:

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.

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

The cycle *C* is thus
{v_{1},*v*_{6},*v*_{2},*v*_{7},*v*_{3},*v*_{4},*v*_{1}}
and the edges in the set *F* are (*v*_{1},*v*_{6}), (*v*_{2},*v*_{6}) and (*v*_{1},*v*_{4}).
The size of *F* is three, but the current value of

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 *x*_{e} 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 *x*_{e} 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
or
.
Then this will give edges around the outside of the graph, together
with the edge (*v*_{3},*v*_{5}).

In particular, starting from *v*_{1} with an empty tree,
we first add edges (*v*_{1},*v*_{4}) and (*v*_{1},*v*_{6}) to the tree.
Growing from *v*_{4} adds the edge (*v*_{4},*v*_{3}).
Growing from *v*_{6} adds the edge (*v*_{2},*v*_{6}).
Growing from *v*_{3} adds the edges (*v*_{3},*v*_{5}) and (*v*_{3},*v*_{7}).
This gives the following tree:

Now growing the tree from vertex *v*_{2} leads to the addition of
edge (*v*_{2},*v*_{7}), 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