3
$\begingroup$

Suppose in a model I have the expression $y_{1}(x) = 10 + 5 x^2$ where $x \in [0,20]$ is a continuous variable. In order to be able to use an MILP solver, I piecewise linearise $z_{1} = x^2$, by choosing $\{0,5,10,20\}$ as arbitrary values for $x$, as follows:

$ x = 0 \lambda_{1} + 5 \lambda_{2} + 10 \lambda_{3} + 20 \lambda_{4} \\ z_{1} =0 \lambda_{1} + 25 \lambda_{2} + 100 \lambda_{3} + 400 \lambda_{4} \\ \lambda_{1} + \lambda_{2} + \lambda_{3} + \lambda_{4} = 1 $

In the same model, I have to deal with the function:

$y_{2}(x,d) = 20 + 5 (x-d)^2, d \ge 0$, $d$ is a variable

Is there a way to express $(x-d)^2$ in a linearised form in terms of $\lambda_{1}, \lambda_{2}, \lambda_{3}, \lambda_{4}$?

Please consider that $y_{1}(x)$ could be any nonlinear function, the quadratic form stated here is just an example.

$\endgroup$
6
  • $\begingroup$ Is $d$ really a variable of the whole model, and not a parameter? (Asking as the function is $y_2(x)$ and not $y_2(x, d)$) $\endgroup$
    – dhasson
    Jun 13, 2020 at 15:42
  • $\begingroup$ d is a decision variable. $y_{2}(x)$ should be written $y_{2}(x,d)$, you are right. $\endgroup$
    – Clement
    Jun 13, 2020 at 17:08
  • $\begingroup$ First, is $x$ constrained to $\lbrace 0, 5, 10, 20\rbrace$ in the model? (Your constraints imply this.) Next, is $d$ discrete, and if so can you enumerate the possible values of $d$. $\endgroup$
    – prubin
    Jun 13, 2020 at 21:23
  • $\begingroup$ The three equations $x= ...$ , $z_{1} = ...$ , $\lambda_{1} + ...$ are supposed to piecewise linear approximate $x^2$ within [0,20]. The points $x=0$, $x=5$, $x=10$, $x=20$ are chosen arbitrarily for this example. $d$ is not discrete. The only constraint imposed on $d$ is $x-d \ge 0.0$. $\endgroup$
    – Clement
    Jun 13, 2020 at 22:44
  • $\begingroup$ $(x-d)^2=x^2 - 2xd + d^2$ and then you can look at or.stackexchange.com/questions/180/… for the middle term. $\endgroup$
    – PSLP
    Jun 15, 2020 at 6:53

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.