Linearize optimization problem with absolute value

126 Views Asked by At

Is there any method to linearize the following optimization problem?

\begin{align} \min_{x,y} &~~ c~[x; y] \\ \text{s.t.} &~~ \sum x\leq \alpha_1 \\ &~~ \sum |y|\leq \alpha_2 \\ &~~ \sum y= 0 \\ &~~ x+|y| \leq 1 \\ &~~ (x,y)\in \{0,1\} \times \{-1,0,1\} \end{align}

EDIT 01/29/2022

Thanks to @RobPratt for the trick.

Is this an equivalent problem?

\begin{align} \min_{x,y,z} &~~ c~[x; y] \\ \text{s.t.} &~~ \sum x\leq \alpha_1 \\ &~~ \sum z\leq \alpha_2 \\ &~~ \sum y= 0 \\ &~~ x+z \leq 1 \\ &~~ y-z \leq 0 \\ &~~ -y-z \leq 0 \\ &~~ (x,y,z)\in \{0,1\} \times \{-1,0,1\} \times\{0,1\} \end{align}

1

There are 1 best solutions below

0
On

For each $y_i$, introduce nonnegative variable $z_i$ to replace $|y_i|$, and impose linear constraints $-z_i \le y_i \le z_i$.