2
$\begingroup$

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?

$\endgroup$

2 Answers 2

4
$\begingroup$

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

$\endgroup$
8
  • 2
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Jun 12, 2022 at 16:08
  • $\begingroup$ Thank you a lot. Looks obvious now that I see it. $\endgroup$ Jun 12, 2022 at 16:18
  • $\begingroup$ same question at stackoverflow.com/questions/72592970/… $\endgroup$ Jun 13, 2022 at 7:15
  • $\begingroup$ @AlexFleischer I posted there first as I didn't this community existed. Is the policy to delete the post in the less specific community? $\endgroup$ Jun 16, 2022 at 12:55
  • $\begingroup$ Hi, no problem. I guess next time the idea is not to cross post. All the best $\endgroup$ Jun 16, 2022 at 13:59
4
$\begingroup$

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);
 }
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.