Feasibility of non convex QCQP

Answered

Giordano Giambartolomei

July 14, 2025 17:18

• 
• 

I am solving an optimisation nonconvex QCP with gurobipy and I am only interested in the feasibility of the region for the problem. Setting m.Params.NonConvex = 2 and some quadratic fake objective to maximise (to help the solver in finding some point), leads gurobi to solve it as an MIP. When the solver starts, it cannot produce any incumbent (it keeps displaying a bar in the corresponding column), and keeps refining the upperbound on the fake objective instead.  Is this a sign of potential infeasibility, or the solver is simply having a hard time finding a feasible point? It's been running for a whole day now, yet no incumbent produced, nor a certificate of infeasibility. Is it eventually going to declare infeasibility through the MIP routine? Shouldn't infeasibility have been spotted at the very start if so?

Related to

• MIP
• Branch-and-Cut

0

• 

  Jaromił Najman

  • Gurobi Staff

  July 15, 2025 08:41

  Hi Giordano,

  leads gurobi to solve it as an MIP

  What exactly do you mean? Do you mean the following output?

  Continuous model is non-convex -- solving as a MIP

  This means that your model is solved via the spatial Branch-and-Bound algorithm. It does not mean that your model is a MIP or is reformulated to a MIP.

  Is this a sign of potential infeasibility, or the solver is simply having a hard time finding a feasible point?

  It could be anything. It is possible that the feasible region of your model is extremely small and thus it is very hard to generate a feasible point.

  Is it eventually going to declare infeasibility through the MIP routine?

  If the model is infeasible, then yes, at some point Gurobi will declare the model infeasible.

  Shouldn't infeasibility have been spotted at the very start if so?

  Unfortunately, not. For non-convex models proving infeasibility can be as challenging as solving them to global optimality.

  Could you please share your model? Maybe there is something that could be done better. Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.

  Best regards, 
  Jaromił

  1
• 

  Giordano Giambartolomei

  July 15, 2025 09:04

  • 
  • 

  Dear Jaromil,

  thank you for addressing all my questions. They were of general character, not just related to a specific model, which I referenced only as an example, so uploading it will not be necessary.

  0

Please sign in to leave a comment.