Skip to main content

The method used in QCQP

Answered
Jin Huang
  • Gurobi-versary
  • First Comment
  • First Question

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

Comments

2 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
  • Jaromił Najman
    • Gurobi Staff

    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

Post is closed for comments.

Didn't find what you were looking for?

New post