What is the Maximum time gurobi takes to find solution
AnsweredI am trying to solve a resource scheduling problem but the gurobi is taking too long time to find the values of decision variables after it has found the optimal value.
I am worried if my objective function and the constraints are written correctly or Is GUROBI taking a long time to find the solution.
Below is the output of GUROBI shared with you. Your valuable input will really be appreciated.
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (win64)
Thread count: 2 physical cores, 4 logical processors, using up to 4 threads
Optimize a model with 6060 rows, 17328 columns and 22615 nonzeros
Model fingerprint: 0x16029718
Model has 1980 quadratic constraints
Model has 2160 general constraints
Variable types: 2160 continuous, 15168 integer (14688 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+02]
QMatrix range [1e+00, 1e+00]
QLMatrix range [1e+00, 1e+00]
Objective range [5e+00, 6e+01]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 7e+02]
Presolve removed 2559 rows and 12975 columns
Presolve time: 0.15s
Presolved: 13357 rows, 7206 columns, 34915 nonzeros
Presolved model has 24 SOS constraint(s)
Variable types: 4071 continuous, 3135 integer (3004 binary)
Found heuristic solution: objective 4025.0000000
Root relaxation: objective 8.748331e+01, 3503 iterations, 0.26 seconds
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time
0 0 87.48331 0 336 4025.00000 87.48331 97.8%  1s
H 0 0 3845.0000000 87.48331 97.7%  1s
H 0 0 3185.0000000 87.48331 97.3%  1s
0 0 107.34167 0 283 3185.00000 107.34167 96.6%  1s
H 0 0 295.0000000 107.34167 63.6%  1s
H 0 0 230.0000000 107.34167 53.3%  1s
0 0 107.58355 0 304 230.00000 107.58355 53.2%  1s
0 0 111.57913 0 301 230.00000 111.57913 51.5%  1s
H 0 0 215.0000000 111.57913 48.1%  1s
0 0 111.61557 0 295 215.00000 111.61557 48.1%  1s
0 0 116.79511 0 194 215.00000 116.79511 45.7%  2s
0 0 117.05838 0 209 215.00000 117.05838 45.6%  2s
0 0 117.05838 0 209 215.00000 117.05838 45.6%  2s
0 0 118.89113 0 257 215.00000 118.89113 44.7%  2s
0 0 118.93124 0 283 215.00000 118.93124 44.7%  2s
0 0 119.89684 0 276 215.00000 119.89684 44.2%  2s
0 0 120.42727 0 269 215.00000 120.42727 44.0%  2s
0 0 120.42746 0 271 215.00000 120.42746 44.0%  2s
0 0 122.55376 0 277 215.00000 122.55376 43.0%  2s
0 0 122.55376 0 237 215.00000 122.55376 43.0%  3s
0 2 122.64509 0 232 215.00000 122.64509 43.0%  3s
14 17 124.88241 8 208 215.00000 123.73723 42.4% 150 5s
H 87 96 195.0000000 123.73723 36.5% 104 6s
H 122 128 190.0000000 123.73723 34.9% 84.1 7s
367 325 136.98460 19 167 190.00000 124.10386 34.7% 80.5 10s
703 599 172.90560 26 130 190.00000 127.92337 32.7% 95.8 15s
794 629 135.40969 10 292 190.00000 135.40969 28.7% 90.0 20s
913 708 141.77083 17 360 190.00000 138.28169 27.2% 78.3 25s
997 764 142.37351 21 413 190.00000 139.85871 26.4% 71.7 31s
1000 769 139.98433 12 403 190.00000 139.98433 26.3% 91.1 39s

Hi Parijat,
I don't understand the issue here. Gurobi has not yet found the optimal (integer feasible) solution  that's why there is still a gap of 26.3% reported. You are possibly referring to the solution of the root LP relaxation. This is not the optimal solution to your mixedinteger problem, though.
Furthermore, the running time presented in your log is far from "long" for such a problem. Keep in mind that you are also including quadratic and general constraints, so your problem is even more difficult to solve than a "simple" MIP which is already NPhard. It is not possible to specify a solving time for any given instance. There are tiny models that may take days to solve while you can solve instances with millions of variables in a few seconds.
Cheers,
Matthias0 
Thanks for your response. Can you please help me understand what the gap is or any relevant article explaining the gap and root relaxation?
In case if it takes days to solve a problem, approximately how many days it may take? I know It depends on the nature and complexity of the problem but I just wanted to know an approximated value if it is a medium complexed problem??
0 
Hi Parijat,
This page is a pretty good introduction to MIP solving and explains the meaning of the gap among other core components:
MixedInteger Programming (MIP)  A Primer on the Basics  Gurobi
Concerning your question about the expected time to optimality: there is no hope of giving a useful and reasonable estimate. This is different for a set of very similar models; here we can expect (but not guaranteee!) a similar time to optimality.
I hope this answers your question.
Cheers,
Matthias0
Please sign in to leave a comment.
Comments
3 comments