Python Pulp 线性规划约束

Question

我对纸浆完全陌生，想知道是否需要优化以下内容：

x = pulp.LpVariable.dicts("Volume", range(0, 7), cat='Binary')

其中只要有 0，则至少需要有 3 个。

所以解可以是 [0,0,0,0,0,0,1], [0,0,0,1,0,0,0], [1,1,1,0,0,0, 1] 但不是 [1,0,1,0,1,0,0]。

我尝试添加一个约束，如下所示：

prob += min([len(list(g)) for k, g in itertools.groupby(x.values()) if k == 0]) >= 3

但没有成功。

我该如何表述呢？

Answer 1

不。PuLP 用于线性规划，因此所有约束都必须是线性的。因此不允许使用 if 语句和类似的编程结构。

具有至少三个连续零的要求可以用不同的方式表达。一种相当有趣的方法是禁止模式 101 和 1001。这可以表示为：

 x[i] - x[i+1] + x[i+2] <= 1             for i=0,1,2,....
 x[i] - x[i+1] - x[i+2] + x[i+3] <= 1    for i=0,1,2,....

这些约束非常精确地排除模式 101 和 1001，但允许任何其他位模式。此外，它们不需要任何额外的变量（其他一些方法需要）。

正如评论中提到的，边界附近发生的事情需要引起注意。其精确实现在一定程度上取决于问题的细节。比如开头允许是01还是001，结尾是否允许是10100。因此，要展示如何做到这一点有点困难（我必须列举几种可能的情况）。

无论如何，这很容易在 Pulp 中表达。