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.