Skip to main content

Always Global Solutions?

Answered

Comments

5 comments

  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    Hi,

    Yes, Gurobi solves optimization problems to global optimality. This is ensured by using an LP-based branch-and-bound method. You can read more about it here.

    Here is a short description of the problem classes that Gurobi can handle.

    Cheers,
    Matthias

    0
  • Aviad Rubinstein

    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
  • Eli Towle
    Gurobi Staff Gurobi Staff

    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
  • Aviad Rubinstein

    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
  • Eli Towle
    Gurobi Staff Gurobi Staff

    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

Please sign in to leave a comment.