The method used in QCQP

Answered

Jin Huang

• February 08, 2022 18:39

Hi,

I firstly modeled my problem as a Mixed-Integer 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 non-convex -- 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? 

0

• 

  Jaromił Najman

  Gurobi Staff

  • February 09, 2022 11:12

  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 non-convex -- solving as a MIP". However, once you make your variables continuous, this reformulation is no longer possible, your model becomes non-convex 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 non-convex MIQCPs, Gurobi uses a spatial branch-and-bound (B&B) algorithm, which is basically the standard MIP B&B but it also allows to branch on continuous variables occurring in non-convex 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.