How to linearize a min-max problem including a variable and parameters? How to linearize the following model: $\min\limits_{x,y}$ $\max\limits_{i \in \\{1, ..., m\\}}(|x-a_i| +b_i)$ s.t. x $\geq$ 0, y $\geq$ 0 where x is a variable and $a_i$ and $b_i$ are parameters I know that I can rewrite the objective function to: $\min\limits_{x,y}$ $\max\limits_{i \in \\{1, ..., m\\}}$ $z(x-a_i) + (1-z)(a_i-x) + b_i$ with the following new set of constraints: s.t. x $\geq$ 0, y$\geq$ 0, $z \in \\{0,1\\}$ Am I now already done with the linearization, or should I still proceed? If so, how?

You are not done with the linearization, you have something quadratic. Besides, you miss some constraints on $z$ which would tell you it is equal to $1$ iff $x-a_i$ is positive. But there is a simpler way to go here...

You can solve the equivalent problem

$\min\limits_{x,y,t} t $ where the variable $t \in \mathbb{R}$

with constraints

$\forall i \in \\{1,..,m\\}, x-a_i+b_i \leq t$

$\forall i \in \\{1,..,m\\}, a_i-x+b_i \leq t$

And the additional constraints you had before.

This is linear, and $t$ will be equal to $\max\limits_i (|x-a_i|+b_i)$

Rq : it is always possible to do something like this when you have a $\max$ or an absolute value (which is a kind of maximum) in the cost function. It is harder when the $\max$ is in the constraints though.