The method used in QCQP
AnsweredHi,
I firstly modeled my problem as a MixedInteger Quadratic Constrained Problem. And Gurobi solves it well. Then I find I can relax all the integer variables(actually {0,1}) to continuous variables (namely [0,1]). This is the only change I have made. I think it should be much faster now. However, after I did this relaxation, it was much slower, and the log file say "Continuous model is nonconvex  solving as a MIP"
So, I am curious about how gurobi solves continuous qcqp problems. Is it solves the continuous qcqp in MIP way? why the continuous problem is slower than the discrete problem?

The binary product of a binary/integer variable with a binary/integer/continuous variable can be linearized to obtain a MIP formulation, see Multiplication of a continuous and a binary variable. Since Gurobi is able to linearize these products and the remaining quadratic terms in your model are convex, you don't see the message "Continuous model is nonconvex  solving as a MIP". However, once you make your variables continuous, this reformulation is no longer possible, your model becomes nonconvex and Gurobi has to now solve an MIQCP instead of a MIP. It is not at all guaranteed that the continuous MIQCP version of your model is any harder or easier than the previous MIP version.
For nonconvex MIQCPs, Gurobi uses a spatial branchandbound (B&B) algorithm, which is basically the standard MIP B&B but it also allows to branch on continuous variables occurring in nonconvex terms. For more details on global optimization and the spatial B&B algorithm, please refer to, e.g., Horst & Tuy 1996.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
1 comment