Integer Programming Constraint For NOR Gate

Question

For a set of binary variables X = {x₁, x₂, ..., x_n} (n>=1). Lets define sum operation for simplicity: sum(X) = x₁ + x₂ + ... + x_n

For another binary variable y, I want to write a constraint or more to represent this NOR behaviour:

• if sum(X) = 0 then y = 1

• if sum(X) > 0 then y = 0

I have achived this behaviour, but my solution needs an extra binary variable z that satisfies y + z = 1

By adding an extra variable I transformed my original requirement to OR gate.

• if sum(X) = 0 then z = 0

• if sum(X) > 0 then z = 1

My solution is:

0 <= n*z − sum(X) <= n−1

y + z = 1

I need another solution that does not require an extra variable.

Answer 1

• Lower Bound for the constraint: 1
• Upper Bound for the constraint: n
• coefficient of variable y for the constraint: n
• coefficients for the variables x for the constraint: 1 for each

Mathematical representation of the constraint: 1 <= ny + sum(X) <= n

If any of the Xs are 1, then y has to be 0; if all of the Xs are 0, then y has to be 1.