# Binary variable constraint

The task is to ensure that if $$x_i = 1$$ for at least $$k$$ of the possible indices $$i$$ in $$\{1,...,n\}$$ then $$y = 1$$, where $$k$$ and $$n$$ are parameters, $$x$$ is a binary variable vector with $$n$$ elements, $$y$$ is a binary variable.

I already tried to build constraints, but it is difficult to me to find the one that ensures the feasibility / infeasibility of certain combinations.

$$\sum_{i=1}^n x_i \leq k-1 + (n-k+1)y$$
• +1. A simple way to derive this is to use the contrapositive $y=0\implies \sum_i x_i \le k-1$ and impose the big-M constraint $\sum_i x_i-(k-1)\le My$, where $M$ is an upper bound on the LHS when $y=1$. Nov 23, 2022 at 13:42
By request, here's an explicit derivation. The desired logical implication is $$\sum_{i=1}^n x_i \ge k \implies y = 1.$$ Its contrapositive is $$y \not= 1 \implies \sum_{i=1}^n x_i < k,$$ equivalently (because $$y$$ is binary and $$\sum_i x_i$$ is an integer), $$y = 0 \implies \sum_{i=1}^n x_i \le k - 1.$$ This logical implication can be enforced via big-M constraint $$\sum_{i=1}^n x_i - (k - 1) \le M y.$$ If $$y=0$$, then $$\sum_{i=1}^n x_i - (k - 1) \le 0$$, as desired. If $$y=1$$, then $$\sum_{i=1}^n x_i - (k - 1) \le M$$, and we want to choose the smallest $$M$$ that makes the constraint redundant, so take $$M$$ to be an upper bound on the left-hand side: $$M = \sum_{i=1}^n 1 - (k - 1) = n - k + 1.$$ The desired constraint is thus $$\sum_{i=1}^n x_i - (k - 1) \le (n - k + 1) y,$$ equivalently, $$\sum_{i=1}^n x_i \le k - 1 + (n - k + 1) y.$$