如何表达线性规划中的“不等于”关系？

Question

我想用库Pulpe（或任何其他工具）来解决Python中的LP问题。在

我想表达一个约束，声明所有变量必须有不同的值，（它们的域是{0，1，2，3。。。N} 对于给定的整数N.），即x_1 != x_2 != x_3 ... != x_N。在

当我不添加任何与我上面提到的约束相关的约束时，解算器会给我一个解决方案，但当我这样做时，它告诉我，即使只有一个解决方案，系统也不可行。在

为了添加“all different”约束，我执行了以下操作：

for x_i in variables:
    for x_j in variables:
        if the following constraint has not been already added and x_i != x_j:
            my_problem += x_i - x_j >= 1, "unique name for the constraint"

以前的代码不起作用。当我想添加约束x_i != x_j时，它就是不起作用。因此，当我处理一组有界整数时，我可以（我想）重写“not equals”为x_I-x_j>；0。Pulpe告诉我它不处理int和{}之间的“>；”运算符，所以我写了x_i - x_j >= 1。然而，它运行，但似乎不起作用，我不知道为什么。在

Answer 1

根据具体情况，有几种方法可以做到这一点。在

您似乎有n变量x[i]。它们可以假定值{0,...,n}，并且必须全部不同。在

顺便说一句：你的符号x[1] ≠ x[2] ≠ x[3]..并不完全正确。E、 g.x[1]=1, x[2]=2, x[3]=1将满足x[1] ≠ x[2] ≠ x[3]。在

所有不同的约束可以成对地写成x[i] ≠ x[j]for all i < j（我们不想检查i和{}两次）。这个不等式可以重述为：x[i] ≤ x[j]-1 OR x[i] ≥ x[j]+1。OR条件可以在MIP模型中实现为：

 x[i] ≤ x[j]-1 + M δ[i,j]        ∀ i < j
 x[i] ≥ x[j]+1 - M (1-δ[i,j])    ∀ i < j
 δ[i,j] ∈ {0,1}

其中M=n+1。我们添加了额外的二进制变量δ[i,j]。在

这是“不平等”结构最直接的表述。它也有相对较少的二进制变量：大约n^2/2。其他配方也可以。有关详细信息，请参见link。在

请注意，约束编程求解器通常具有针对所有不同约束的内置工具，因此使用CP解算器可能更容易（对于具有所有不同约束的模型，它们也可能更高效）。在

Answer 2

您的约束不起作用的原因是您要求x_i至少比x_j大1，对于每个i和{}。所以您需要x_1 > x_2和{}。您可以通过在if语句中将x_i != x_j替换为i > j或类似的东西来解决这个问题。在

但在您的例子中，我会考虑使用二进制变量来指示每个x_i取哪个值。例如，让y_{i,n} = 1如果x_i = n。那么你就有一个约束

sum {i=1,...,N} y_{i,n} <= 1全部n = 0,...,N

（即n的每个值最多只能使用一次）和其他类似的

sum {n=0,...,N} y_{i,n} = 1全部i = 1,...,N

（必须为每个i分配一些值n）。在

然后，在公式中，将所有x_i变量替换为sum {n=0,...,N} y_{i,n}。在