Modeling Mutual Exclusion with Binaries

Learn to translate mutual-exclusion rules — pairwise incompatibility, group-level 'at most one' or 'exactly one' selection, and logical implications of the form 'if A then not B' — into linear constraints on binary variables.

Step 1 of 157%

Tutorial

Pairwise Mutual Exclusion

Two decisions are mutually exclusive if at most one of them may be selected. Using binary variables $x_1, x_2 \in \{0,1\}$ (where $x_i = 1$ means option $i$ is selected and $x_i = 0$ means it is not), the mutual-exclusion rule is captured by

x_1 + x_2 \leq 1.

The constraint forbids the combination $(x_1, x_2) = (1,1)$ , whose sum is $2$ . The other three binary combinations $(0,0), (1,0), (0,1)$ all satisfy the inequality.

Notice that the 'do nothing' outcome $(0,0)$ remains feasible. If the problem instead requires that exactly one of the two options be selected, we use the equality form

x_1 + x_2 = 1.

For instance, if a company must choose between supplier $A$ and supplier $B$ but cannot use both, and is allowed to use neither, the constraint is $y_A + y_B \leq 1$ with $y_A, y_B \in \{0,1\}$ .