Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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 $$
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.$$
