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, 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_Scouse
    Jun 24, 2020 at 18:04
  • $\begingroup$ OK, it might help to show the full model. $\endgroup$
    – RobPratt
    Jun 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_Scouse
    Jun 24, 2020 at 19:52

1 Answer 1

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, 2020 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, 2020 at 15:14
  • $\begingroup$ This is interesting, but I can’t understand why the term $2x_0(x-x_0)$? $\endgroup$
    – Kuifje
    Jun 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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.