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?

  • 4
    $\begingroup$ You could convert it to MILP, but it will be easier to solve it separately on each interval and the the better result. $\endgroup$ – Michal Adamaszek Oct 29 '19 at 10:03
  • $\begingroup$ If the feasible region were $[x_1, x_2]$, would you be able to write it as an LP? $\endgroup$ – 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}

  • $\begingroup$ This argument is too simple. Sometimes you can apply a transformation of variables to turn a nonconvex set into a convex one. Not saying that that is the case here, but I do not see the value of your answer compared to the comments already posted. $\endgroup$ – LinAlg Oct 29 '19 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.