IBM CPLEX目标函数中如何使用XOR实现Max-Cut问题建模

你不需要更换现有的建模思路，一开始给每个顶点定义布尔决策变量的方向完全正确，异或判定逻辑不需要引入特殊运算，用常规数学规划表达式即可实现。

首先明确基础变量定义：

• 对图中每个顶点i，定义0-1决策变量x_i：x_i=1代表顶点i属于选取的顶点子集S，x_i=0代表顶点i不在S中。

针对你卡住的“边{a,b}在割集时取1、否则取0”的异或逻辑，有两种成熟的标准写法，适配不同求解场景：

二次0-1规划形式（实现最简洁） #

异或结果可以直接用如下二次项等价表示：
x_a + x_b - 2*x_a*x_b

你可以直接代入所有可能的取值验证正确性：

• x_a=0, x_b=0：计算结果为0，对应两点同属一个集合，边不在割集
• x_a=0, x_b=1：计算结果为1，对应两点分属不同集合，边在割集
• x_a=1, x_b=0：计算结果为1，对应两点分属不同集合，边在割集
• x_a=1, x_b=1：计算结果为0，对应两点同属一个集合，边不在割集

此时Max-Cut的模型可以直接写为无约束二次0-1规划形式：

max  sum_{{a,b}∈E} (x_a + x_b - 2*x_a*x_b)
s.t. x_i ∈ {0,1}  对所有顶点i∈V

如果你的求解器支持二次整数规划，直接输入该模型即可求解，不需要额外加变量或约束。

线性整数规划形式（适配线性MIP求解器） #

如果你使用的是仅支持线性模型的混合整数规划求解器，可以给每条边额外引入一个0-1辅助变量y_{ab}，标记边{a,b}是否属于割集（y_{ab}=1表示在割集，0表示不在），再通过线性约束绑定异或逻辑即可。

对每条边{a,b}添加如下4个线性约束：

• y_{ab} ≤ x_a + x_b
• y_{ab} ≤ 2 - x_a - x_b
• y_{ab} ≥ x_a - x_b
• y_{ab} ≥ x_b - x_a

这组约束可以严格保证y_{ab}的取值和x_a XOR x_b的结果完全一致，此时模型写为：

max  sum_{{a,b}∈E} y_{ab}
s.t. 对所有边{a,b}∈E，满足上述4个y与x的绑定约束
     x_i ∈ {0,1}  对所有顶点i∈V
     y_{ab} ∈ {0,1}  对所有边{a,b}∈E

补充：如果做大规模问题的近似求解，你还可以把0-1变量x_i替换为取值±1的变量z_i = 2x_i - 1，此时异或项可以简化为(1 - z_a*z_b)/2，这也是Max-Cut半定规划松弛的标准表达形式。

内容的提问来源于stack exchange，提问作者Moritz Groß