4
$\begingroup$

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

$\endgroup$
8
$\begingroup$

@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 \\ $$

$\endgroup$
1
  • $\begingroup$ Thanks @RobPratt, these conjunctive normal forms are always very helpful. $\endgroup$ – Kuifje Mar 2 at 17:11
8
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.