I would like to linearize $x^2$ term in my objective function. I understand this can be solved using quadratic programming solver; however, for my use case linearization is necessary to convert it to MIP if possible. Any help is much appreciated.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ What is the motivation to convert to MIP? $\endgroup$– RobPrattJun 24, 2020 at 17:57
-
$\begingroup$ Terms similar to $x^2$ are part of a larger MIP problem and I think the part of the objective function with the power terms are slowing down the solution. So I wanted to see if converting them to pure MIP will reduce the computation time. $\endgroup$– S_ScouseJun 24, 2020 at 18:04
-
$\begingroup$ OK, it might help to show the full model. $\endgroup$– RobPrattJun 24, 2020 at 18:58
-
$\begingroup$ I am not able to share the full model due to some confidentiality reason. If possible, I would appreciate any method to linearize power terms. $\endgroup$– S_ScouseJun 24, 2020 at 19:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
There are two possibilities that come to mind, assuming that $x$ is a continuous variable. One is to do a piecewise-linear approximation (leading to an answer that is, well, approximate). The other is to replace $x^2$ with a new variable $z$ and then, on the fly, add constraints of the form $z \ge x_0^2 + 2x_0(x-x_0)$ when a solution is obtained containing $x_0$ and $z_0$ with $z_0 \lt x_0^2$. The latter method is potentially useful if the nature of the model precludes the solver choosing $z \gt x^2$. With CPLEX, you can add these constraints in a lazy constraint callback. With a solver that lacks the needed callback structure, you would be in a solve - cut - solve cycle until you got an optimal solution needing no further cuts.
-
-
$\begingroup$ Interesting. But is there much chance that doing all this lazy constraint callback jazz in CPLEX is better than just submitting the problem to CPLEX as an MIQP? $\endgroup$ Jun 25, 2020 at 15:14
-
$\begingroup$ This is interesting, but I can’t understand why the term $2x_0(x-x_0)$? $\endgroup$– KuifjeJun 25, 2020 at 21:21
-
1$\begingroup$ @MarkL.Stone: Absent other complications in the model, no, but S_Scouse wants to linearize for undisclosed reasons. (And the callback stuff isn't jazz, it's more of a country - rap hybrid.) $\endgroup$– prubin ♦Jun 25, 2020 at 23:52
-
1$\begingroup$ @Kuifje: Charitably assuming I did my calculus correctly, that should be the formula for the tangent to $f(x)=x^2$ at $x=x_0$. $\endgroup$– prubin ♦Jun 25, 2020 at 23:53