# Modeling a constraint such that a set of binary decision variables do not equate to 1 simultaneously

I would like to seek some advice on modeling the following logical condition:

I would like to ensure that a group of binary variables do not equate to 1 simultaneously, i.e., $$\omega_{1}=1, \omega_{2}=1,\cdots,\omega_{n}=1$$ is unaccepted.

On the other hand, the values for $$\omega_{1},\omega_{2},\cdots,\omega_{n}$$ can take any permutation of 0s and 1s, e.g. $$\omega_{1}=1,\omega_{2}=1,\cdots,\omega_{n}=0$$.

## 2 Answers

@Kuifje's formulation is correct. Here's a somewhat automatic derivation via conjunctive normal form: $$\lnot \bigwedge_{i=1}^n \omega_i \\ \bigvee_{i=1}^n \lnot \omega_i \\ \sum_{i=1}^n (1 - \omega_i) \ge 1 \\ \sum_{i=1}^n \omega_i \le n-1 \\$$

• Thanks @RobPratt, these conjunctive normal forms are always very helpful. – Kuifje Mar 2 at 17:11

How about $$\omega_1 + \cdots + \omega_n \le n-1$$

This way, at most all variables but one of them can take value $$1$$ simultaneously.

In the context of knapsack problems, if each variable models the selection of a given item and that the sum of the weights of the items exceed the knapsack capacity, these inequalities are called cover inequalities.