How to implement v=(a==b) using Linear Programming? $$ v= \begin{cases} True, a=b\\ False, a≠b\\ \end{cases} $$

Until now I tried the big M-Method.

To show a≤b: $$a-b+Mv≤M$$ $$-a+b-Mv≤-1$$

To show b≤a: $$-a+b+Mv≤M$$ $$a-b-Mv≤-1$$

When they are equal everything is okay, but when a≠b it doesn't work.


1 Answer 1


Use Cast to boolean, for integer linear programming, setting $x=a-b$ and $y=v$. This only works if you have a constant upper bound on $|a-b|$. Otherwise, I don't know how to express it in an ILP.

See also Express boolean logic operations in zero-one integer linear programming (ILP), Boolean variable true iff equation is satisfied in ILP, Boolean variable that captures whether an inequality holds.

  • $\begingroup$ I forgot to mention because I thought it was irrelevant but 1<=|a|,|b|<=10. $\endgroup$
    – Adamos2468
    May 6, 2019 at 4:57

Your Answer

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

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