How to linearize max, min, and abs functions

In this post you will see how to linearize max functions, min functions, and absolute value functions. These can be expressed mathematically as:

X \leq max(A, B)

X \geq min(A, B)

X \geq |A|

Let’s start with the modulus, as the other two depend on it.

X \geq |A|

Here you simply replace that one constraint by the following two:

X \geq A

X \geq -A

The min function can be linearized as:

X \geq min(A, B)

First, we decompose the min function into a max and a modulus.

X \geq max(A, B) - |A - B|

Then we get rid of the max.

X \geq A - |A - B|

X \geq B - |A - B|

Finally, the answer is using the following five constraints:

X \geq A - S^- - S^+

X \geq B - S^- - S^+

S^- \geq B - A

S^+ \geq A - B

S^-, S^+ \geq 0

Remember to penalize S^- and S^+ such that only one of them will be different from zero in any solution.

The max function can be linearized as follows:

X \leq max(A, B)

X \leq min(A, B) + |A-B|

From here on things are very similar to the min function…

X \leq A + |A - B|

X \leq B + |A - B|

And finally, the five necessary constraints are:

X \leq A + S^- + S^+

X \leq B + S^- + S^+

S^- \geq B - A

S^+ \geq A - B

S^-, S^+ \geq 0

And again, remember to penalize S^- and S^+.

Thanks to Lieke van der Heide.

This was useful? Buy me a cup of coffee to help me keep this website running!