MAX-CUT to integer programming

Question

I'm trying to understand MAX-CUT to IP, but I can't find the steps between them.

So we have a MAX CUT problem and then you can turn it into this problem

MAXCUT: $maximize_{x}$ $\frac{1}{4} \sum_{i=1}^{n} \sum_{j=1}^{n} w_{ij} (1-x_{i}x_{j})$ s.t. $x_{j} \in \{-1,1\}$, j=$1, \ldots , n$.

The problem is I don't understand how you get this. Also I can't find any where that explains this.

Answer 1

I guess what you want is max-cut in an undirected graph. In the given formulation, the vertices are partitioned into two sets based on whether $x_i$ is $1$ or $-1$. Then, we can see that for all edges $(i,j)$ within the same block of vertices, $(1-x_ix_j)$ will be $0$. So only those edges which are across the blocks remain in the summation. And for these edges $(i,j)$, $(1-x_ix_j)=2$. Also each edge is counted twice, once as $(i,j)$ and once as $(j,i)$. So the required cut value is $1/4$ of the summation.

For max-cut in directed graphs, look at this LP formulation for min-cut. We can modify it to get the ILP formulation for max-cut as (assuming the weights $w_{ij}$ are all non-negative)

$$ \begin{array}{rcll} & & max \sum_{(i,j) \in E} w_{ij}d_{ij} & \\ d_{ij}-p_i+p_j & \geq & 0 & (i,j) \in E\\ p_i & \in & \{0,1\} & i \in V \\ d_{ij} & \in & \{0,1\} & (i,j) \in E \end{array} $$

Answer 2

Here's probably a working ILP version borrowed from the notes.

\begin{equation} \begin{aligned} \text{maximize:} & \sum_{(i,j) \in E} w_{ij} e_{ij} \\ \text{subject to:} & \enspace e_{ij} \leq x_i + x_j \,\, \forall (i,j) \in E\\ & \enspace e_{ij} \leq 2 - (x_i + x_j) \,\, \forall (i,j) \in E\\ & \enspace x_i,x_j \in \{0,1\} \,\, \forall i,j \in V \\ & \enspace e_{ij} \in \{0,1\} \,\, \forall (i,j) \in E \end{aligned} \end{equation}