0
$\begingroup$

I'm trying to linearize the problem:

$\max f(x)\\\text{s.t.}\\g(x)\geq 0$

Where $g(x)$ are already linear functions, but $f(x)$ is the following piecewise function:

$f(x)=\begin{cases} bx, & \text{if } x < c \\[2ex] 0, & \text{if } x = c \\[2ex] -ax, & \text{if } x>c \end{cases}$

With $a,b,c>0$ constants.

This seems very easy, but I'm having a hard time to find a solution. So, I would be very thankful for any help!

$\endgroup$
2
$\begingroup$

You can introduce three binary variables, one for each piece, a constraint that they sum to 1, and additional linear constraints that link the binary variables to $f(x)$, but it is simpler to just solve three separate problems and take the max.

If $x\in[L,U]$ and $\epsilon>0$ is a tolerance, impose linear constraints \begin{align} z_1+z_2+z_3&=1\\ L z_1+c z_2+(c+\epsilon)z_3 \le x &\le (c-\epsilon)z_1+c z_2+U z_3\\ -M(1-z_1)\le f-b x &\le M(1-z_1)\\ -M(1-z_2)\le f&\le M(1-z_2)\\ -M(1-z_3)\le f+a x&\le M(1-z_3) \end{align}

$\endgroup$
  • $\begingroup$ Thank you Rob. I cannot solve them separately, because it is part of a scheduling problem, and the total cost is in fact the sum of T problems of this type. Therefore I think I must add the binary variables. I started modelling with one binary for each piece. However, I'm not sure how to link $f(x)$ to them. Something like: $f(x) = \lambda_1(bx) + \lambda_2(0) + \lambda_3(-ax)$? What about the limits $c$? $\endgroup$ – Luciana Marques Nov 10 '19 at 0:31
  • $\begingroup$ No, that would still be nonlinear because of the products of variables. I updated the answer just now. $\endgroup$ – Rob Pratt Nov 10 '19 at 11:10
  • $\begingroup$ Makes sense. Thank you! $\endgroup$ – Luciana Marques Nov 13 '19 at 22:29

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.