Always Global Solutions?
AnsweredI am new to Gurobi and cannot find the answer in the manual and here. Does Gurobi always guarantee global solutions for all kinds of optimization programs it can solve? If yes, could you briefly tell me how it guarantees?

I have a followup question:
I have a small optimization problem with quadratic constraints (it's a nonconvex domain unfortunately).
Can Gurobi guarantee optimality of the solution? How?The response above by Matthias suggests it can (quadratic constraints are included in the list of problem classes), but the post about "how" is only about linear constraints/objectives.
0 
Yes, Gurobi solves nonconvex quadratic problems to global optimality, subject to the specified optimality tolerance. Gurobi solves such problems using a spatial branchandbound algorithm. The NonConvex Quadratic Optimization webinar discusses Gurobi's approach in more detail.
As a short example, say we have the constraint \( z = x\cdot y \), where \( x \in [\ell_x, u_x] \) and \( y \in [\ell_y, u_y] \). Gurobi constructs an LP relaxation of the problem using the four corresponding McCormick constraints:
$$\begin{align*}z &\geq \ell_yx + \ell_xy  \ell_x\ell_y\\ z &\geq u_yx + u_xy  u_xu_y\\ z &\leq \ell_yx + u_xy  u_x\ell_y\\ z &\leq u_y x + \ell_xy  \ell_xu_y.\end{align*}$$
If the relaxation solution doesn't satisfy \( z = x \cdot y \) (within some tolerance), then Gurobi branches on \( x \) or \( y \). In the child nodes, the domain of the corresponding variable is reduced. Gurobi picks an open node, constructs a new (tighter) McCormick relaxation using the refined variable bounds, then solves the node in the hope that \( z = x \cdot y \). Gurobi repeats this process as necessary until the global primal and dual bounds are sufficiently close. Overall, the approach is very similar to classical MIP branchandbound, but instead of branching to find relaxation solutions that satisfy integrality constraints, the solver branches to find relaxation solutions that satisfy bilinear constraints like \( z = x\cdot y \).
0 
Thanks Eli for the response, this is super helpful!
Followup question: How can I get Gurobi to output the branchandbound log so that I can verify the proof?
0 
Gurobi doesn't return a certificate of optimality that you can use to manually verify that the solution to your nonconvex problem is optimal. You have access to the optimal solution, which can be used to confirm Gurobi's final primal bound. As for the dual bound, you can monitor this in the log output. The initial dual bound is the optimal value of the root relaxation solve. This dual bound is then improved with cutting planes and as Gurobi explores the branchandbound tree. Branchandbound tree information can be found in the log output or via callbacks, but you won't be able to completely reconstruct Gurobi's full branchandbound tree or view the specific cuts Gurobi adds. This wouldn't even be particularly helpful, because Gurobi doesn't expose the mapping between the original and presolved models.
You should see the branchandbound log output by default. If you're using a thirdparty API, you might need to explicitly set Gurobi's OutputFlag parameter to 1 or enable logging with a special option. Here is a snippet of the log output of Gurobi 9.5.2 solving the nonconvex pooling problem from the webinar I linked:
Root relaxation: objective 2.100000e+03, 5 iterations, 0.01 seconds (0.00 work units)
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time
0 0 2100.00000 0 4 0.00000 2100.00000   0s
H 0 0 99.9999995 2100.00000 2000%  0s
0 0 2100.00000 0 4 100.00000 2100.00000 2000%  0s
0 0 2100.00000 0 4 100.00000 2100.00000 2000%  0s
0 0 2100.00000 0 4 100.00000 2100.00000 2000%  0s
H 0 0 112.5000000 2100.00000 1767%  0s
0 2 2100.00000 0 4 112.50000 2100.00000 1767%  0s
* 13 8 4 375.4697900 963.80806 157% 4.6 0s
H 27 14 378.4672573 444.59113 17.5% 3.1 0s
H 33 18 382.6859986 444.59113 16.2% 2.6 0s
H 38 26 389.1641517 444.59113 14.2% 2.4 0s
H 43 24 390.9695946 444.59113 13.7% 2.1 0s
H 67 24 396.5759156 404.81838 2.08% 1.5 0s
H 83 28 397.0035015 402.52489 1.39% 1.3 0s
H 86 28 397.0076639 402.52489 1.39% 1.2 0s
H 94 28 399.2295768 401.59309 0.59% 1.1 0s
H 109 26 399.7726790 400.87500 0.28% 1.0 0s
* 125 32 28 399.7739309 400.87500 0.28% 1.1 0s
* 198 56 27 399.7930897 400.27994 0.12% 0.9 0s
* 212 54 26 399.7934758 400.20252 0.10% 1.0 0s
* 252 76 37 399.8216964 400.13520 0.08% 1.0 0s
* 303 98 33 399.8247706 400.08069 0.06% 1.1 0s
* 323 98 30 399.9860057 400.08069 0.02% 1.1 0s
* 381 108 29 399.9891327 400.00927 0.01% 1.2 0s
H 412 108 399.9999166 400.00072 0.00% 1.2 0s
* 413 108 23 400.0000009 400.00072 0.00% 1.2 0s
Cutting planes:
RLT: 7
Explored 425 nodes (545 simplex iterations) in 0.10 seconds (0.01 work units)
Thread count was 4 (of 4 available processors)
Solution count 10: 400 400 399.989 ... 399.773
Optimal solution found (tolerance 1.00e04)
Best objective 4.000000008500e+02, best bound 4.000007244079e+02, gap 0.0002%Gurobi tracks the objective value of the incumbent solution (the primal bound) in the "Incumbent" column. The best dual bound is reported in the "BestBd" column. For this problem, the root relaxation LP yielded a dual bound of 2100, which Gurobi was quickly able to improve to ~400 by cutting and branching. You can read more about logging in the MIP logging section of the documentation.
0
Please sign in to leave a comment.
Comments
5 comments