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

6
$\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$
    – RobPratt
    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$
    – I.A
    Feb 1, 2023 at 12:03
  • $\begingroup$ @I.A I added an answer just now. $\endgroup$
    – RobPratt
    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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.