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?
Best Answer
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}