Always Global Solutions?
Answered
I 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?
-
Official comment
-
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 why not try our AI Gurobot?. -
-
I have a follow-up 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 non-convex quadratic problems to global optimality, subject to the specified optimality tolerance. Gurobi solves such problems using a spatial branch-and-bound algorithm. The Non-Convex 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 branch-and-bound, 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!
Follow-up question: How can I get Gurobi to output the branch-and-bound 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 non-convex 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 branch-and-bound tree. Branch-and-bound tree information can be found in the log output or via callbacks, but you won't be able to completely reconstruct Gurobi's full branch-and-bound 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 branch-and-bound log output by default. If you're using a third-party 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 non-convex 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.00e-04)
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 -
Post is closed for comments.
Comments
6 comments