Question on global optimality certification for nonconvex MIQCP (bilinear terms + binaries)

回答済み

培松 刘

2026年01月14日 07:06 編集済み

• 
• 

Dear  Gurobi Support Team,

I have a nonconvex mixed-integer quadratic model and would like to confirm whether Gurobi can certify a true global optimum.

Model framework (abstract)

Variables:

• Continuous: x ∈ [xL, xU], y ∈ [yL, yU], c ∈ [cL, cU], d ∈ [dL, dU]
• Binary: q ∈ {0,1}^m
• Continuous auxiliaries: r, t

Key nonlinearity: 

• Bilinear terms c* y, so the model is nonconvex.（x is fixed）

Typical constraint pattern (for each i):

• r≤ d − cx + M q
• r≤ M (1 − q)
• t≤ av− b (d− cy)
  with bounded variables and a big-M formulation.

Objective:

• Linear terms in (x, y, c, d, r, t) plus terms involving r and t; nonconvexity only comes from bilinear uy .

We solve with:

• NonConvex = 2
• All variables are explicitly bounded (x,y,c,d have finite bounds); M is a finite constant.

Questions

 

1. Can Gurobi solve this model to global optimality?
2. If Gurobi returns Status=OPTIMAL and reports MIPGap=0 (or within tolerance), does this certify a globally optimal solution for this nonconvex MIQCP/MIQCQP class (bilinear terms + binaries), assuming all variable bounds are finite?
3. Are there required modeling conditions to ensure valid global bounds/certification (e.g., explicit bounds on all continuous variables involved in bilinear terms; avoiding very large M; etc.)?

Best regards,
Liu

関連

• MIQCP
• MINLP

1

• 

  Byron Tasseff

  • Gurobi Staff

  2026年01月16日 17:23

  Hi Liu,

  Thank you for the detailed description. Models with bilinear terms and integer variables fall into the class of nonconvex MIQCP/MIQCQP problems that Gurobi handles with a global algorithm.

  (1) Can Gurobi solve this model to global optimality?

  Yes. Starting with Gurobi 9.0, Gurobi supports general nonconvex quadratic constraints/objectives (including bilinear terms). In versions prior to 11.0, you must set NonConvex=2 to enable optimization of nonconvex quadratic models. From 11.0 onward, nonconvex quadratic models can be solved with NonConvex left at its default setting. The "Quadratic Constraints" section of the documentation notes the following:

  The algorithms in Gurobi explore the entire search space, so they provide a globally valid lower bound [in minimization problems] on the optimal objective value, and given enough time they will find a globally optimal solution (subject to tolerances).

  (2) If Status=OPTIMAL and MIPGap=0 (or within tolerance), is that a global certificate?

  Yes. A status of OPTIMAL indicates that the model was solved to optimality within solver tolerances. For these nonconvex quadratic models, Gurobi's global algorithm maintains a globally valid objective bound. When the incumbent and global bound meet the termination criterion (e.g., MIPGap/MIPGapAbs), OPTIMAL certifies that the solution satisfies optimality, feasibility, and integrality tolerances. If you see numerical warnings, you can also inspect solution quality metrics (constraint/bound/integrality violations) in addition to relying on status.

  (3) Are there modeling conditions required to ensure valid bounds/certification?

  There are no additional special modeling requirements, but a few best practices are important for performance and numerical robustness:

  • Provide finite and as-tight-as-possible bounds for variables, especially those that appear in bilinear terms.
  • Choose big-M values as tight as possible. Overly large big-M values can weaken relaxations and cause numerical issues.
  • If you are concerned about numerics, it can be useful to inspect solution quality metrics alongside the status code.

  For additional background, you may find our "Non-convex Quadratic Optimization" webinar helpful.

  I hope this helps! Please let me know if you have any additional questions.

  1
• 

  培松 刘

  2026年01月18日 04:42

  • 
  • 

  Thank you very much for the clear and detailed explanation. This fully addresses my questions and is very helpful for our work.

  0

サインインしてコメントを残してください。