Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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$.
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.
@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 \\ $$
