Either-Or Constraints¶

Definition¶

To require at least one of $\boldsymbol{a}^{\top}\boldsymbol{x}\le b$ and $\boldsymbol{d}^{\top}\boldsymbol{x}\le e$ $e$ , introduce $y\in\{0,1\}$ and write

\boldsymbol{a}^{\top}\boldsymbol{x}\le b+My,\qquad \boldsymbol{d}^{\top}\boldsymbol{x}\le e+M(1-y).

The finite constant $M$ must be large enough that the relaxed inequality imposes no unintended restriction over the relevant variable domain.

Interpretation¶

Either-or constraints require a solution to satisfy at least one of two inequalities. A binary variable $y$ decides which inequality is enforced, and a large constant $M$ switches the other one off. Points satisfying both are also allowed, so this is the inclusive "or".

Two overlapping shaded regions, each satisfying one of two constraints, with points (7, 1) and (1, 7) in one region each and the point (5, 5) in neither; their union is not convex.

The blue region satisfies $3x_1+2x_2\le18$ $18$ , the red region $x_1+4x_2\le16$ $16$ , and the allowed set is their union. The point $(1,7)$ gives $17\le18$ but $29>16$ $16$ , so it is allowed with $y=0$ $0$ , which enforces the first inequality. The point $(7,1)$ gives $23>18$ but $11\le16$ $16$ , so it needs $y=1$ $1$ . The point $(5,5)$ violates both and is excluded whatever $y$ is.

With $y=0$ the second inequality becomes $\boldsymbol{d}^{\top}\boldsymbol{x}\le e+M$ $M$ , which should hold for every relevant $\boldsymbol{x}$ and so restricts nothing; for $y=1$ the roles swap. Hence $M$ must cover the largest amount by which the switched-off left-hand side can exceed its right-hand side. If $M$ is too small, allowed points are cut away; a much larger $M$ is still correct but weakens the LP relaxation, where $y$ may be fractional.

The binary variable is needed: the union contains $(7,1)$ and $(1,7)$ but not their midpoint $(4,4)$ , since $20>18$ and $20>16$ $16$ . A system of linear inequalities always contains the average of any two of its points (see convex combinations), so none in $x_1,x_2$ alone describes this set. With several binaries the same device gives K-out-of-N constraints and nonconvex region modelling.

Key Results¶

For $y=0$ $0$ , the first inequality is enforced; for $y=1$ $1$ , the second is enforced.
A valid value of $M$ requires information about bounds on the expressions being relaxed.
This is a modelling device; it does not mean multiplying two decision variables.

Examples¶

The blue inequality is enforced when $y=0$ $0$ , and the red one when $y=1$ $1$ . The illustrated union is nonconvex, so it cannot be represented by one system of continuous linear inequalities in $\boldsymbol{x}$ alone.

$3x_1+2x_2\le18+My$ and $x_1+4x_2\le16+M(1-y)$ implement the video example.
The week 3 exercise applies the same switch to two inequalities involving four variables.

Prerequisites¶

Sources¶

OR Modelling · Week 3

Aliases: disjunctive constraints Symbols: element of

Last updated: 22 October 2026 19:04