3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ What is the motivation to convert to MIP? $\endgroup$
    – RobPratt
    Jun 24 '20 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_Scouse
    Jun 24 '20 at 18:04
  • $\begingroup$ OK, it might help to show the full model. $\endgroup$
    – RobPratt
    Jun 24 '20 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_Scouse
    Jun 24 '20 at 19:52
6
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thank you, very useful. $\endgroup$
    – S_Scouse
    Jun 24 '20 at 20:46
  • $\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 '20 at 15:14
  • $\begingroup$ This is interesting, but I can’t understand why the term $2x_0(x-x_0)$? $\endgroup$
    – Kuifje
    Jun 25 '20 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 '20 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 '20 at 23:53

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.