0

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.

simplicity
  • 3,694
  • What information are you looking for? If you want to understand the relation to max cut in a graph $G=(V,E)$, consider that each cut $(S, V\setminus S)$ in $G$ corresponds to the solution $x$ where $x_i = 1$ iff $i\in S$. The correspondence is invertible and preserves cost. So the IP exactly captures the max cut instance. If you want to understand this approach more generally, google for explanations of the semi-definite program for max-cut. – Neal Young Aug 14 '17 at 18:59

2 Answers2

0

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}

Akshay Bansal
  • 371
-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} $$

polkjh
  • 1,432
  • 1
    This LP doesn't work for max cut, does it? You can simply set $d_{ij} = 1$ for all $i,j$. (And you can't easily fix it by reversing the first inequality, because then you'd have $d_{ij} + d_{ji} <= (-p_i + p_j) + (-p_j + p_i) = 0$, so all $d_{ij}$'s would have to be zero.) – Neal Young Aug 14 '17 at 18:44
  • 1
    Per this paper, this is the standard LP relaxation: $$\begin{array}{rcll} {\max \sum_{ij} w_{ij} d_{ij}} \text{ subject to}\ d_{ij} & \le & d_{ik} + d_{kj} & (i,j,k) \ d_{ij} + d_{ik} + d{kj} & \le & 2 & (i,j,k)\ d_{ij} & \in & [0,1] & (i,j).\end{array}$$ – Neal Young Aug 19 '17 at 21:31
  • This formulation won't work with the same reason as given by @NealYoung. – Akshay Bansal Jul 13 '22 at 02:46
  • @AkshayBansal, if you mean the LP formulation in my comment, note that the $d_{ij}=1$ solution (for all $i, j$) is not feasible because of the second constraint. I guess you could set $d_{ij}=2/3$ to show a large integrality gap, though. – Neal Young Jul 13 '22 at 13:29
  • @NealYoung: Apologies, I don't think I communicated it well. The LP in your comment is perfectly fine. I just intended to say the the LP of the accepted answer is incorrect. Added a new answer which is more or less your LP but a bit descriptive. – Akshay Bansal Jul 13 '22 at 15:04