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

Question

我想用库 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. 但是，它运行但似乎不起作用，我不知道为什么。

Answer 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。其他配方也是可能的。有关更多信息，请参阅链接。

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