# Absolute value minimization with non-convex constraint

I want to solve the following optimization problem in $$x\in\mathbb{R}$$

$$\begin{array}{ll} \text{minimize} & |ax+b|+|cx+d|\\ \text{subject to} & x \in [x_1,x_2] \cup [x_3,x_4]\end{array}$$

where $$[x_1,x_2] \cap [x_3,x_4]=\emptyset$$. Is there a way to transform it to a LP form?

• You could convert it to MILP, but it will be easier to solve it separately on each interval and the the better result. – Michal Adamaszek Oct 29 '19 at 10:03
• If the feasible region were $[x_1, x_2]$, would you be able to write it as an LP? – Rodrigo de Azevedo Oct 29 '19 at 11:48

Because the feasible region is nonconvex, you cannot model it as a single linear program. Here's a MILP formulation: \begin{align} \text{minimize} &&y_1+y_2\\ \text{subject to} &&y_1 &\ge ax+b \\ &&y_1 &\ge -(ax+b) \\ &&y_2 &\ge cx+d \\ &&y_2 &\ge -(cx+d) \\ &&x_1 (1-z) + x_3 z &\le x \le x_2 (1-z) + x_4 z\\ &&z &\in \{0,1\} \end{align}