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

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

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

当我没有添加与上面提到的内容有关的任何约束时，求解器为我提供了一个解决方案，但是当我这样做时，它告诉我该系统即使有一个解决方案也不可行。

为了添加“所有不同”约束，我做了以下工作：

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时，它根本不起作用。因此，当我使用一组有界整数时，我可以（我认为）将“不等于”重写为x_i-x_j>0。Pulpe告诉我，它不处理int与LpAffineExpression所以我写了x_i - x_j >= 1。但是，它可以运行，但似乎不起作用，我不知道为什么。

最佳答案

有几种方法可以执行此操作，具体取决于实际情况。

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

顺便说一句：您的符号x[1] ≠ x[2] ≠ x[3]..并不完全正确。例如。 x[1]=1, x[2]=2, x[3]=1将满足x[1] ≠ x[2] ≠ x[3]。

可以将所有x[i] ≠ x[j]的所有约束均成对写入i < j（我们不想两次检查i和j）。可以将不等式重新定义为：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求解器可能会更容易（对于具有所有约束的模型，它们也可能更有效）。