Converting conditional constraints to linear constraints in Linear Programming

Question

I have two variables: x>= 0 and y binary (either 0 or 1), and I have a constant z >= 0. How can I use linear constraints to describe the following condition:

If x = z then y = 1 else y = 0.

I tried to solve this problem by defining another binary variable i and a large-enough positive constant U and adding constraints

y - U * i = 0;
x - U * (1 - i) = z;

Is this correct?

Answer 1

Really there are two classes of constraints that you are asking about:

1. If y=1, then x=z. For some large constant M, you could add the following two constraints to achieve this:

x-z <= M*(1-y)
z-x <= M*(1-y)

If y=1 then these constraints are equivalent to x-z <= 0 and z-x <= 0, meaning x=z, and if y=0, then these constraints are x-z <= M and z-x <= M, which should not be binding if we selected a sufficiently large M value.

2. If y=0 then x != z. Technically you could enforce this constraint by adding another binary variable q that controls whether x > z (q=1) or x < z (q=0). Then you could add the following constraints, where m is some small positive value and M is some large positive value:

x-z >= mq - M(1-q)
x-z <= Mq - m(1-q)

If q=1 then these constraints bound x-z to the range [m, M], and if q=0 then these constraints bound x-z to the range [-M, -m].

In practice when using a solver this usually will not actually ensure x != z, because small bounds violations are typically allowed. Therefore, instead of using these constraints I would suggest not adding any constraints to your model to enforce this rule. Then, if you get a final solution with y=0 and x=z, you could adjust x to take value x+epsilon or x-epsilon for some infinitesimally small value of epsilon.