3
$\begingroup$

I have a problem with linear constraints but in the objective function I want to have some linear terms along with a $x^2$ term. So it is like the following:

$$\min \sum \limits _i \sum \limits _j (a[i,j] + b[i,j]^2)$$

$ a[i,j] $ and $ b[i,j]$ are integer decision variables.

All my constraints are linear. So my question is, how I can linearize the quadratic objective function and convert the problem to a linear one.

I had an idea to convert it to piecewise linear function, with derivatives at specific points, but I am looking for another solution, as my problem includes many binary and integer variables, and adding more it will make it more complex and slow to solve.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I would try first with an MIQP solver. These are readily available, e.g. through neos-server.org/neos. $\endgroup$
    – Erwin Kalvelagen
    Commented Dec 1, 2022 at 13:32
  • $\begingroup$ Thanks for the recommendation, but I have a working model in python and Xpress, and I am working on the redefinition of the objective function. $\endgroup$
    – christouandr7
    Commented Dec 1, 2022 at 15:57
  • $\begingroup$ Xpress can solve problems with a convex quadratic objective (which yours is). $\endgroup$
    – prubin ♦
    Commented Dec 1, 2022 at 16:52
  • $\begingroup$ Ah ok, thanks for that. So you recommend to use the quadratic term in the objective function instead of linearizing it? Which one would be faster? I would prefer speed over accuracy, so I would go also with a good approximation. $\endgroup$
    – christouandr7
    Commented Dec 1, 2022 at 17:21
  • $\begingroup$ @christouandr7, just try that. :) $\endgroup$
    – A.Omidi
    Commented Dec 3, 2022 at 11:16

0

Reset to default

Your Answer

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