8
$\begingroup$

I was wondering what types of methods can be used to strengthen QCQP relaxations.

Our solver has all the standard stuff, like constraint propagation, presolving, etc., but some QCQP problems seem to be taking forever to converge to global optimality unless we throw 400 CPUs at them, even with strong branching.

Specifically for QCQPs, we are using RLT and convexity cuts to strengthen the relaxations, but it feels there might be something more to the story.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ have you looked at these papers?: "Relaxations and Randomized Methods for Nonconvex QCQPs", "General Heuristics for Nonconvex Quadratically Constrained Quadratic Programming", "Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation". $\endgroup$
    – Oguz Toragay
    Mar 6, 2020 at 17:08
  • $\begingroup$ OSQP? osqp.org $\endgroup$
    – Richard
    Mar 7, 2020 at 19:12

3 Answers 3

Reset to default
6
$\begingroup$

Sometimes cuts from Boolean Quadric Polytope can help: https://link.springer.com/article/10.1007/s12532-018-0133-x

Improve this answer
$\endgroup$
2
$\begingroup$

Have you tried using SOCP relaxation instead of RLT?

Improve this answer
$\endgroup$
2
$\begingroup$

Gurobi has some slides on what they did in the recent 9.0 version, which added the support for qcqp. It is not much and highlevel, but it might be still beneficial.

https://pages.gurobi.com/rs/181-ZYS-005/images/2020-01-14_Non%20Convex%20Quadratic%20Optimization%20in%20Gurobi%209.0%20Webinar.pdf

There is even a video for the slides:

https://www.gurobi.com/de/resource/non-convex-quadratic-optimization/

Improve this answer
$\endgroup$

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.