How to model y <= max(x₁,x₂) in Linear Programming?

In my courses at Ghent University (for the course Applied Operations Research) or Vlerick Business School (for the courses Decision Sciences or Taking Sound Business Decisions), I explain my students how the big M method works, and I ask them to model the equation y <= max(x₁,x₂) in a Linear Programming model.

But today, an MBA student at Peking University gave me a solution that does not require a big M constraint. It goes as follows:

The question is: How to maximize y
subject to
y <= max(x₁,x₂)

Everybody should know that y <= max(x₁,x₂) is not a linear equation but it is the same as y <= min(x₁,x₂)+abs(x₁-x₂).

The first part (min(x₁,x₂)) is easy to linearize, so it will become like this:

y <= x₁ + |x₁ - x₂|
y <= x₂ + |x₁ - x₂|

with |x₁ - x₂| the absolute value of x₁ - x₂.

But the problem is that the absolute value |x₁ - x₂| is not linear as well.

However, making absolute values linear is simple, just take a look at the following link here. 

Conclusion: You can easily make this nonlinear absolute value linear, and by integrating everything, you should be able to build a model that exactly does what it need to do.

How elegant, isn't it?

Author of this solution: One of my students in the FT BiMBA at Peking University (2013)
Ce (Jack) Wang
MBA Candidate
Beijing International MBA at Peking University (BiMBA)
National School of Development (NSD)
Peking Univeristy

Thank you Jack!

Download our free ORASTalks app to receive more tips and hints on topics like this!