5
$\begingroup$

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.

$\endgroup$

2 Answers 2

5
$\begingroup$

$$ \sum_{i=1}^n x_i \leq k-1 + (n-k+1)y $$

$\endgroup$
3
  • 2
    $\begingroup$ +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$. $\endgroup$ Commented Nov 23, 2022 at 13:42
  • $\begingroup$ @RobPratt I could not understand why: k-1 and n-k+1 as big-M??would be grateful for an answer $\endgroup$ Commented Feb 1, 2023 at 12:03
  • $\begingroup$ @I.A I added an answer just now. $\endgroup$ Commented Feb 2, 2023 at 1:22
6
$\begingroup$

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.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.