How to model Max-Cut as ILP

Question

I want to model Max-Cut in IBM's CPLEX, but I fail at modeling the objective function. My attempt is to use is to sum the XOR of inclusion for vertices of each edge, as exactly then an edge is included in the cut. But I don't see a way to use XOR.

Is there another way to model Max-Cut that is feasible in CPLEX?

Answer 1

Let $V$ and $E$ be the sets of vertices and edges respectively. Define a binary variable $x_v$ for each vertex $v\in V$ to be 1 if the vertex is on the "left" side of the cut and 0 if it is on the "right" side. Define a variable $y_{(i,j)}\in [0,1]$ for each edge $(i,j)\in E.$ (You can make $y$ either binary or continuous.) Your objective function is to maximize $$\sum_{(i,j)\in E} y_{(i,j)}$$and your constraints are $$y_{(i,j)}\le x_i + x_j \quad \forall (i,j)\in E$$ and $$y_{(i,j)}\le 2 - x_i - x_j \quad \forall (i,j)\in E.$$

Answer 2

To start with maxcut, you can start with the maxcut example in how to with OPL ?

int n=400;
range r=1..n;

// Random graph  
float edge_prob=0.5;
int  weight_range=10;
int big=100000;
 
tuple t
{
  int i;
  int j;
}

{t} s={<i,j> | ordered i,j in r};

int w[i in r][j in r]=(i<=j)?((rand(big)<=big*edge_prob)?rand(weight_range):0):0;

// end of random graph

//int n=4;
//range r=1..n;
//float w[r][r]=
//
//[[ 0. , 8. ,-9. , 0.],
// [ 8. , 0. , 7. , 9.],
// [-9. , 7.  ,0., -8.],
// [ 0. , 9., -8. , 0.]];

assert card(s)==n*(n-1) div 2;

 // x is the unknown and 0 or 1 means in one or the other side of the fence
 dvar boolean x[r];
 
 dexpr float obj=2*sum(<i,j> in s) w[i][j]*x[i]*(1-x[j]);
 
 maximize obj;
 
 subject to
 {
   
 }
 
 {int} x1={i| i in r:x[i]==1};
 
 execute
 {
   writeln("objective = ",obj);
   writeln("x set to 1 : ",x1);
 }