# How to model Max-Cut as ILP

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?

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.$$

• It turns out that these are exactly the constraints that arise somewhat automatically from rewriting $y_{(i,j)} \implies ((x_i \lor x_j) \land \neg (x_i \land x_j))$ in conjunctive normal form. Jun 12, 2022 at 16:08
• Thank you a lot. Looks obvious now that I see it. Jun 12, 2022 at 16:18
• same question at stackoverflow.com/questions/72592970/… Jun 13, 2022 at 7:15
• @AlexFleischer I posted there first as I didn't this community existed. Is the policy to delete the post in the less specific community? Jun 16, 2022 at 12:55
• Hi, no problem. I guess next time the idea is not to cross post. All the best Jun 16, 2022 at 13:59

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);
}