Modeling At-Most-K and Exactly-K Constraints

Suppose we have binary decision variables $x_1, x_2, \ldots, x_n \in \{0,1\}$, where $x_i = 1$ means item $i$ is selected and $x_i = 0$ means it is not.

The at-most-K constraint restricts the number of selected items to at most $K$. Since each selected item contributes $1$ to the sum and each unselected item contributes $0$, the total count of selected items is exactly $\sum_{i=1}^n x_i$. We therefore write

$$\sum_{i=1}^n x_i \leq K, \quad \text{i.e.,} \quad x_1 + x_2 + \cdots + x_n \leq K.$$

For example, with five binaries $x_1, \ldots, x_5$, the requirement "at most $2$ of them equal $1$" becomes

$$x_1 + x_2 + x_3 + x_4 + x_5 \leq 2.$$

The assignment $(x_1, x_2, x_3, x_4, x_5) = (1, 0, 1, 0, 0)$ has sum $2$ and is feasible. The assignment $(1, 1, 1, 0, 0)$ has sum $3$ and is infeasible.