Solution Method and Runtime
Answered
Hi dear Gurobi Support Team,
As a student who has recently started implementing models, I am currently working on solving a Vehicle Routing Problem (VRP), where I have linearized some constraints beforehand. As I progress with my implementation, I have encountered a couple of questions for which I would greatly appreciate your assistance.
Firstly, I am unsure about the solution method used by Gurobi to solve the problem. I would like to understand where I can find information about the specific solution method employed and whether this information is somewhere available in the generated log file.
Secondly, I have been monitoring the runtime of my optimization process. I have noticed that the reported solve time (model.Runtime) was 0. I have measured positive elapsed times using start=timer() before building the model and end=timer() after calling the optimize() function and because of that I'm not sure if a runtime of 0 is correct. Considering that I optimize the model multiple times – solving, checking the solution, and adding constraints iteratively – I am unsure why the reported runtime remains zero. I must note that I conducted preliminary tests using a small example, and while the 'elapsed time' reported is indeed positive, it is extremely close to zero (0.02849 seconds).
Thank you very much for your attention and support.
Regina :)
-
Hello Regina,
I’ll address each of your queries regarding the solution method and runtime issues when using Gurobi.
Solution Method Used by Gurobi
-
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 columns
Presolve time: 0.01s
Presolved: 242 rows, 260 columns, 1295 nonzeros
Variable types: 0 continuous, 260 integer (260 binary)
Root relaxation: objective 1.23456e+03, 335 iterations, 0.02 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1234.5600 0 67 - 1234.5600 - - 0s
H 0 0 1300.000000 1234.5600 5.04% - 0s
H 0 0 1290.000000 1234.5600 4.33% - 0sIn 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 algorithmThe methods are: -1 - Automatic, 0 - Primal Simplex, 1 - Dual Simplex, 2 - Barrier,
3- Concurrent, 4 - Deterministic Concurrent.Runtime Reporting
-
Runtime of 0 Explanation:
- Gurobi’s
model.Runtimereports the optimization time excluding model building.
- Gurobi’s
-
Measuring Time Correctly:
- When measuring time using
time(), ensure you are capturing the time around theoptimize()call correctly, excluding model building time. Here’s how to do it:
- When measuring time using
from time import time
# model building here excluded from timer
start = time()
model.optimize()
end = time()
elapsed_time = end - start
print("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
- As further reading, you may find this thread interesting.
- 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
0 -
-
Hallo,
Thank you for your help!
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
0 -
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
0 -
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
0 -
Hi Regina,
Yes, the method used here is Branch-and-Cut.
Best regards,
Elisabeth
0
Please sign in to leave a comment.
Comments
5 comments