K-Out-of-N Constraints¶

Definition¶

To require at least $K$ of $N$ inequalities $\boldsymbol{a}_i^{\top}\boldsymbol{x}\le d_i$$d_i$, introduce binary relaxation indicators $y_i$ and impose

Here $0\le K\le N$ and $M$ must validly relax each marked inequality. The video's equality $\displaystyle \sum_i y_i=N-K$ gives the same allowed $\boldsymbol{x}$ values when such relaxation is valid.

Interpretation¶

The K-out-of-N construction requires enough conditions from a list to hold, without saying in advance which ones. Each indicator $y_i$ can release one inequality, at most $N-K$ inequalities may be released, and so at least $K$ remain enforced. A released inequality is allowed to hold as well.

Here $N=4$ and $K=2$$2$. The switches $y_2$ and $y_4$ equal $1$, so the second and fourth inequalities are released, while $y_1=y_3=0$ keeps the first and third enforced. The bound $y_1+y_2+y_3+y_4\le2$ forbids releasing a third one, so at least two of the four inequalities always hold.

Each part has one job. With $y_i=0$ the term $My_i$ disappears and $\boldsymbol{a}_i^{\top}\boldsymbol{x}\le d_i$ is enforced; with $y_i=1$ the right-hand side grows by $M$, which must be large enough to impose no restriction on the relevant values of $\boldsymbol{x}$. For $N=2$ and $K=1$ this is the either-or construction, where the two indicators are $y$ and $1-y$$y$. The counting constraint is the same kind of bound on a sum of binary variables as in mutually exclusive decisions.

Mind the direction: $y_i=1$ means that inequality $i$ is released, not that it holds. Read the other way round, $\displaystyle \sum_iy_i\le N-K$ would seem to say that at most $N-K$ inequalities hold, the opposite of what is intended. The construction also does not make exactly $K$ inequalities true, since a released inequality may still be satisfied.

Key Results¶

• The formulation does not require exactly $K$ original inequalities to be true.
• The practice solution uses the inequality version; the video uses equality.
• For $K=N$$N$, no constraint may be relaxed.

Examples¶

The figure sets $N=4$$4$, $K=2$$2$: the binary bound $y_1+y_2+y_3+y_4\le2$ allows at most two released inequalities, leaving at least two enforced. The constant $M$ must be large enough to remove unintended restrictions from every released inequality.

• At least two of four constraints can be enforced using $y_1+y_2+y_3+y_4\le2$$2$.
• At least two of three constraints leave at most one relaxation indicator equal to 1.

Prerequisites¶

• Either-Or Constraints

Related Concepts¶

• Finite-Value Constraint
• Nonconvex Region Modelling

Sources¶

• OR Modelling · Week 3

Symbols: sum

Last updated: 20 October 2026 03:02