• Gurobi Staff

Hello Regina,

I’ll address each of your queries regarding the solution method and runtime issues when using Gurobi.

Solution Method Used by Gurobi

1. Identifying the Solution Method:

• Log File: When you run an optimization with Gurobi, the solver's log file typically provides detailed information about the optimization process, including the solution method used. For a VRP, which is generally modeled as a Mixed Integer Programming (MIP) problem, Gurobi uses Branch-and-Cut. You can read more details on the algorithm and its different components (Presolve, Cutting Planes, Heuristics...) in Mixed-Integer Programming (MIP) - A Primer on the Basics.

To find this information in the log file, look for lines mentioning "Presolve", "Method", or "Cuts applied". Here’s an example snippet from a Gurobi log file:

Presolve removed 28 rows and 17 columnsPresolve time: 0.01sPresolved: 242 rows, 260 columns, 1295 nonzerosVariable types: 0 continuous, 260 integer (260 binary)Root relaxation: objective 1.23456e+03, 335 iterations, 0.02 secondsNodes    |    Current Node    |     Objective Bounds      |     WorkExpl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time0     0 1234.5600    0   67          - 1234.5600      -     -    0sH    0     0                    1300.000000 1234.5600  5.04%     -    0sH    0     0                    1290.000000 1234.5600  4.33%     -    0s

In the above log, "Root relaxation" refers to the linear programming relaxation of the MIP, which is part of the Branch-and-Bound method.

2. Method Details:

You can explicitly set the method Gurobi uses via the Method parameter:

model.setParam('Method', 1)  # Use primal simplex algorithm

The methods are: -1 - Automatic, 0 - Primal Simplex, 1 - Dual Simplex, 2 - Barrier, 3 - Concurrent, 4 - Deterministic Concurrent.

Runtime Reporting

1. Runtime of 0 Explanation:

2. Measuring Time Correctly:

• When measuring time using time(), ensure you are capturing the time around the optimize() call correctly, excluding model building time. Here’s how to do it:
from time import time# model building here excluded from timerstart = time()model.optimize()end = time()elapsed_time = end - startprint("Elapsed time: {:.5f} seconds".format(elapsed_time))print("Gurobi Runtime: {:.5f} seconds".format(model.Runtime))

3. Precision of output. You may be getting an exact 0 when using model.Runtime because of the precision when printing very small runtimes like 0.02849 seconds. Make sure that you use enough precision like in the code snippet above.

Recommendations

• Testing Larger Instances: Try with larger, more complex instances of the VRP to see if the solve time remains negligible. Larger instances should provide a more realistic benchmark for timing.

If you continue to see discrepancies in runtime or have other questions about specific Gurobi features or parameter settings, please feel free to ask. The more detailed the logs and your observations, the better the community or support team can assist in optimizing your implementation.

Kind regards,

Gurobot

Hallo,

I'm still a bit confused about the solution method that Gurobi uses when solving an MIP.  Before the screenshot, you said that the branch-and-cut-method is used to solve the Problem. However the website you linked to talkes about the Branch-and-Bound-Method.  I'm a bit unsure, maybe you could help me again. Root relaxation is mentioned in my log file.  Does this mean that Branch and Bond was used?

Kind regards,

Regina

• Gurobi Staff

Hi Regina,

I understand your confusion, this was not completely clear in the Gurobot reply. Branch-and-cut is essentially branch-and-bound with the addition of using Cutting Planes to tighten the Linear Programming relaxations. This is what Gurobi does to solve MIPs. Solving the root relaxation is necessary both for branch-and-bound and for branch-and-cut.

Feel free to share a logfile if you need help understanding specific parts of it.

Best regards,

Elisabeth

Hello Elisabeth,

Thank you for your response. I wanted to mention in my thesis what solution method was used to solve the problem. Did I understand correctly that Branch-and-Cut is used here to solve the MIP?

Best regards,

Regina

• Gurobi Staff

Hi Regina,

Yes, the method used here is Branch-and-Cut.

Best regards,

Elisabeth