constraintslogical-operatorslinear-programmingnor

Integer Programming Constraint For NOR Gate


For a set of binary variables X = {x1, x2, ..., xn} (n>=1). Lets define sum operation for simplicity: sum(X) = x1 + x2 + ... + xn

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

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.

My solution is:

0 <= n*z āˆ’ sum(X) <= nāˆ’1

y + z = 1

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


Solution

  • 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.