0
$\begingroup$

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?

$\endgroup$
2
  • 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, 2019 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, 2019 at 11:48

1 Answer 1

Reset to default
3
$\begingroup$

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}

$\endgroup$
1
  • $\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, 2019 at 18:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .