2
$\begingroup$

I have the following two logical implications. $x_{it}$ and $y_{it}$ are binary, $N$ is an integer number. $i$ and $k$ are indexes. $$\sum_{k=1}^{t}x_{ik}\ge N~\implies y_{it}=1$$ $$\sum_{k=1}^{t}x_{ik}< N~\implies y_{it}=0 $$ How can I represent these implications as constraints?

$\endgroup$
1

2 Answers 2

3
$\begingroup$

You can model the two implications as follows: $$ N\cdot y_{it} \le \sum_{k=1}^{t}x_{ik}\le t+(N-1-t)\cdot(1-y_{it}) $$

$\endgroup$
3
  • $\begingroup$ I think you beat me by a couple of second :-) $\endgroup$
    – Sune
    Commented Apr 25 at 12:27
  • $\begingroup$ Lets call it a tie $\endgroup$
    – Kuifje
    Commented Apr 25 at 12:28
  • $\begingroup$ Thanks to both of you. I was wondering how I can integerate $t$ as it is an index? $\endgroup$ Commented Apr 25 at 16:53
0
$\begingroup$

Given upper and lower bounds on $\sum_{k=1}^t x_{ik}$, say $l$ and $u$, you can enforce your bi-implication $\sum_{k=1}^t x_{ik}\geq N\iff y_{it}=1$ using the inequalities \begin{equation} \sum_{k=1}^t x_{ik}\geq l+(N-l)y_{it} \end{equation} and \begin{equation} \sum_{k=1}^t x_{ik}\leq u - (u-(N-1))(1-y_{it}) \end{equation} If $y_{it}=1$, then the first inequality gives $\sum_{k=1}^t x_{ik}\geq N$ and the second gives $\sum_{k=1}^t x_{ik}\leq u$. If $y_{it}=0$, on the other hand, then we have $l\leq \sum_{k=1}^t x_{ik}\leq N-1$.

$\endgroup$
10
  • $\begingroup$ Note that since $x$ is binary, $l=0$ and $u=t$. $\endgroup$
    – Kuifje
    Commented Apr 25 at 12:26
  • $\begingroup$ Yes. But maybe you have stronger bounds derived from other parts of whatever model this comes from $\endgroup$
    – Sune
    Commented Apr 25 at 12:29
  • 3
    $\begingroup$ Also I think you have typo in the second constraint, it should be $(u-(N-1))$ $\endgroup$
    – Kuifje
    Commented Apr 25 at 12:31
  • $\begingroup$ you are right. Typo corrected $\endgroup$
    – Sune
    Commented Apr 25 at 12:52
  • $\begingroup$ Thanks to both of you. I was wondering how I can integerate $t$ as it is an index? $\endgroup$ Commented Apr 25 at 19:06

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.