linear-programming - 如何将其转换为一组线性约束？

Question

例如，给定一个二进制变量的一维数组

x = [0,1,0,0,1] 

我想创建一个新变量y，这样y <= max(x). 换句话说

y = 0只有当sum(x) = 0.

y = 1只有当sum(x) > 0.

如何将其转换为一组线性约束？

我知道这一定是可能的，因为 IBM CP Optimizer Suite 可以自动处理它，但我无权访问它。

Answer 1

尝试像 y <= sum(x) 这样简单的方法，如果所有 x 都为零，它将强制 y 为零。

然后，为了将 y 强制为 1，您有多种选择。您可以简单地为 x 中的每个变量添加一个 y >= x 的约束，或者使用像 My >= sum(x) 这样的大 M 约束，其中 M 是某个常数，它是 x 中可以同时相等的变量的最大数量到 1. 添加单独的约束可能会提供更紧密的线性松弛，尤其是在有许多 x 变量的情况下。