在整数线性规划约束内使用最小/最大运算符

Question

我有以下整数变量 x1、x2、x3 和 y1、y2、y3。 有没有办法通过以下方式来约束它们？

例如：

min(x1, x2, x3) + min(y1, y2, y3) <= 100

或

max(x1, x2, x3) / 5 + max(y1, y2, y3) / 5 >= 50

Answer 1

在第一个场景中，您对最小值施加“向下压力”。如果你想说的话那就简单多了

max(x1, x2, x3) + max(y1, y2, y3) <= 100

在这种情况下，您将需要 2 个辅助变量来通过约束捕获

x

和

y

的最大值，然后对这 2 个辅助变量求和。您正在走“艰难的路”，您需要强制选择

x

和

y

各 1 个。因此，您需要一些二进制变量来强制执行该选择。

考虑仅使用

x

的简化情况：

min(x1, x2, x3) <= 25

让：

select_x[j] ∈ {0, 1} represent the selection of x[j] as the minimum

然后我们就有了

∑ select_x[j] * x[j] <= 25

我们需要一个约束来强制必须至少选择 1 个：

∑ select_x[j] >= 1

类似地，对于

y

，你会得到类似的结果：

∑ select_x[j] * x[j] + ∑ select[k] * y[k] <= 100

意识到，这现在是一个非线性整数程序。如果您的问题很小，这可能没问题，但在更大范围内可能很难解决。幸运的是，我认为你可以用大 M 约束将其线性化......

对于“只是x”的例子，我们可以重新表述为

x[j] <= select_x[j] * 25 + (1 - select_x[j]) * M  [for all j]

并且通过一点布尔逻辑，我们可以制作一组

j x k

约束来获得 min(x) + min(y) 总和：

x[j] + y[k] <= (select_x[j] + select_y[k])/2 * 100 + (2 - select_x[j] - select_y[k]) * M  [for all j, k]

在这种情况下，M 应该 > max(x) + max(y)

您应该能够翻转此逻辑，添加另一组选择变量并对第二个约束执行相同的操作。