Linearization of if-then constraint

Question

I'm trying to linearize a constraint of this form: if a == b then c = 1 where a and b are positive integers and c is a binary variable. I'm looking for a solution like this one https://math.stackexchange.com/questions/2792360/how-to-linearize-if-then-constraint which doesn't work in this case. Thanks to anyone who can help me.

@not_speshal cannot do that. I'm plugging the constraint onto Pyomo and I need a precise mathematical linear formulation — Unziello
– Unziello, Commented Aug 19, 2021 at 14:19
It wasn't clear to me why that other solution wouldn't work in your case. Can you explain why not? Did you try it, or does it just seem wrong because it is framed the other way around? — TMBailey
– TMBailey, Commented Aug 19, 2021 at 16:42
@TMBailey Pyomo requires constraint expressions to return unnested expression objects. Returning an expression with a nested expression (a==b) fails to compile. Besides, the if commonly used in programming doesn't qualify as a linear expression... try to see it as a sort of step function, where you have a certain x threshold where the y value changes, it is clearly nonlinear. — Unziello
– Unziello, Commented Aug 19, 2021 at 16:53
@Unziello you should include that comment in your question. It's much more helpful to know why it doesn't work in this case. Include all relevant information in your question, since people might miss information given in a comment — pho
– pho, Commented Aug 19, 2021 at 17:26

Erwin Kalvelagen · Accepted Answer · 2021-08-19 21:29:22Z

3

The implication

 a = b => c = 1

 (a,b: integer variables, c: a binary variable)

can be re-stated as:

 c = 0 => a >= b + 1 
          or
          a <= b - 1

(Using that a,b are integers). An "or" needs an extra binary variable. So we can write:

 a >= b + 1 - M δ - M c
 a <= b - 1 + M (1-δ) + M c
 δ ∈ {0,1}

Here M is a large enough constant (to be chosen with care).

answered Aug 19, 2021 at 19:01

Erwin Kalvelagen

16.9k3 gold badges18 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Nice. pyomo seems to want the variables in constraints to all appear on the same side of the inequality, but that's easily done.

No, Pyomo does not require that.