1
$\begingroup$

I want to write the following constraint: If A=1 and B <= m then C=1 ( where A and C are binary, m is a constant and B is continuous).

$\endgroup$
1
$\begingroup$

My solution requires some kind of hack in the model, a Big-$M$ value, which is pretty common, but also a tolerance $\varepsilon$, which is not very desirable. I hope that I do not miss something easy here but reckon there is no way around it.

To model a condition of the form $(X \wedge Y) \to Z$ for binary $X, Y, Z$, you can use $$\tfrac12(X + Y) \leq Z + \tfrac12.$$ We can verify this by inserting: $X=Y=1$ yields to $1$ on the left hand side, thus, $Z$ has to be at least $\frac12$, and since it is binary, it must be $1$. If either $X$ or $Y$ is $0$ (or both), we have at most $\frac12$ on the left hand side and in this case $Z$ might be either $0$ or $1$.

We also need to transform the constraint $B \leq m$ as a binary variable in order to use the template above. This can be done by introducing a new binary variable $B'$ which must assume the vaue $1$ iff $B \leq m$. We also need a Big-$M$ value which must be greater than any value that $B$ can assume (note that for numerical reasons in practice, $M$ should be not too large). Moreover, we have $\varepsilon$, a small tolerance value to get a strict $>$-inequality (in practice you would choose the difference to the next greater number from $m$ that can be represented exactly on your machine). We now add the constraints $$B \leq m + (1-B')M\tag{1}$$ $$B \geq m + \varepsilon - B'M\tag{2}$$ $(1)$ guarantees that $B' = 0$ if $B > m$, $(2)$ guarantees that $B' = 1$ if $B \leq m$. We verify this again: If $B \leq M$, $(1)$ and $(2)$ can be satisfied with $B' = 1$, but not with $0$. If $B > m$, we need $B' = 0$ to satisfy $(1)$ and then $(2)$ is satisfied since $B$ is at least $\varepsilon$ larger than $m$.

Putting it all together, we obtain your constraint $$ \tfrac12(A + B') \leq C + \tfrac12,\\ B \leq m + (1-B')M,\\ B \geq m + \varepsilon - B'M. $$

$\endgroup$
  • $\begingroup$ Thanks for your reply. So is B' an auxiliary binary variable? $\endgroup$ – bcv Jul 8 at 22:51
  • $\begingroup$ Yes $B'$ is a new binary variable that does not occur anywhere else in your IP. $\endgroup$ – ttnick Jul 9 at 5:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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