IBM CPLEX在目标函数中使用XOR

Question

我想建模 max-cut 图形的问题。

当您需要选择顶点子集时，我的方法是用布尔决策变量编码每个顶点。

我的问题是目标函数：Edge {a，b}如果其一个顶点之一在子集中，而另一个位于另一个顶点，则确切地在剪切中，这是逻辑 xor 。

我看不到目标函数中的“ 1 if xor（a，b）else 0”的方法。方法是否应该完全不同？

Answer 1

z = x xor y可以写为线性不等式系统：

  z ≤ x+y
  z ≥ x-y
  z ≥ y-x
  z ≤ 2-x-y 

Answer 2

在所有API中，您可以使用逻辑构造，然后写XOR。

例如，在OPL中：

dvar boolean x;
dvar boolean y;
dvar boolean xxory;

subject to
{
  xxory==(x+y==1);
  xxory==1;
}

要从MaxCut开始，您可以从 maxcut示例< /a> in 如何使用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);
 }