求无需额外变量的NOR门整数规划约束表达式

变量定义 #

• 二进制变量集合：X = {x₁, x₂, ..., xₙ}（n≥1，每个xᵢ ∈ {0,1}）
• 求和表达式：sum(X) = x₁ + x₂ + ... + xₙ
• 输出二进制变量：y ∈ {0,1}，需满足NOR逻辑：
  • 当sum(X) = 0时，y = 1
  • 当sum(X) > 0时，y = 0

无额外变量的整数规划约束 #

直接用以下两个线性整数约束即可实现需求，无需引入额外变量：

1. sum(X) ≤ n*(1 - y)
2. n*y ≤ n - sum(X)

约束逻辑验证 #

• 当sum(X) = 0时：
  • 约束1：0 ≤ n*(1 - y)，恒成立，对y无限制
  • 约束2：n*y ≤ n，即y ≤ 1，结合y是二进制变量，此时y只能取1，符合NOR要求
• 当sum(X) ≥ 1时：
  • 约束1：sum(X) ≤ n*(1 - y)，因sum(X)≥1，若y=1则右边为0，矛盾，故y只能取0
  • 约束2：n*y ≤ n - sum(X)，y=0时左边为0，右边n - sum(X) ≥ 0（sum(X)≤n），恒成立，符合NOR要求

内容的提问来源于stack exchange，提问作者Jengador