Crazy MIP search tree exploration
Answered
Yesterday I was experiencing a very strange behaviour while teaching.
I have a simple cutting stock compat (Kantorovich) model and a simple instance and I solve with my pc with more than 20,000 nodes explored, in hundreds of seconds. My students use the same code and solve it in less than 2,000 nodes and 3 seconds.
I have shared with them the mps file to be sure we have the same problem. Both used gurobi_cl filename.mps.
I have also modified the model (mps) by giving a different order to the variables: the general behaviur is different, since with the original mps the first heuristic find a solution 238, while with the second it finds 263, but the exploration of the tree is again very different.
I made the check with two students. Same behavior.
I post here the log files, since I cannot attach files. Random decisions inside the MIP search justify the different behavior of the two students, but not the very bad behavior in my pc. I repeated the test several times, resetting the pc and also uninstalling and reinstalling Gurobi
============== my pc ===================
Using license file C:\Users\Mauro\gurobi.lic
Set parameter LogFile to value gurobi.log
Academic license - for non-commercial use only
Gurobi Optimizer version 9.0.3 build v9.0.3rc0 (win64)
Copyright (c) 2020, Gurobi Optimization, LLC
Read MPS format model from file csc.mps
Reading time = 0.02 seconds
cutting-stock: 603 rows, 2400 columns, 4200 nonzeros
Optimize a model with 603 rows, 2400 columns and 4200 nonzeros
Model fingerprint: 0x1d6d7bfe
Variable types: 0 continuous, 2400 integer (600 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+01]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [2e+02, 3e+02]
Presolve time: 0.02s
Presolved: 603 rows, 2400 columns, 4200 nonzeros
Variable types: 0 continuous, 2400 integer (600 binary)
Found heuristic solution: objective 238.0000000
Root relaxation: objective 2.200000e+02, 981 iterations, 0.02 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 220.00000 0 216 238.00000 220.00000 7.56% - 0s
0 0 220.00000 0 256 238.00000 220.00000 7.56% - 0s
0 0 220.00000 0 243 238.00000 220.00000 7.56% - 0s
0 0 220.00000 0 215 238.00000 220.00000 7.56% - 0s
0 0 220.00000 0 215 238.00000 220.00000 7.56% - 0s
0 2 220.00000 0 223 238.00000 220.00000 7.56% - 0s
809 389 235.71429 182 142 238.00000 235.71429 0.96% 52.3 5s
1335 492 cutoff 37 238.00000 235.78571 0.93% 72.5 10s
2082 635 236.14286 67 41 238.00000 235.78571 0.93% 77.3 15s
3140 1123 236.78571 94 55 238.00000 235.78571 0.93% 81.0 20s
4308 1629 235.92857 74 67 238.00000 235.78571 0.93% 79.7 25s
5865 2360 cutoff 71 238.00000 235.80357 0.92% 76.6 30s
7087 3089 236.92177 137 61 238.00000 235.85714 0.90% 77.2 35s
8466 3755 235.92857 31 57 238.00000 235.85714 0.90% 75.5 40s
9643 4481 237.00000 98 54 238.00000 235.85714 0.90% 77.0 46s
10787 4738 237.00000 86 33 238.00000 235.87755 0.89% 77.6 52s
11445 4999 cutoff 74 238.00000 235.92857 0.87% 80.0 56s
12491 5560 cutoff 140 238.00000 235.92857 0.87% 81.4 60s
14312 6471 cutoff 107 238.00000 235.92857 0.87% 78.8 65s
15912 7094 cutoff 85 238.00000 235.92857 0.87% 78.4 71s
16868 7506 cutoff 78 238.00000 235.94898 0.86% 79.8 75s
18292 8241 237.00000 132 34 238.00000 235.95714 0.86% 79.1 80s
19220 8822 236.21429 109 33 238.00000 235.96939 0.85% 78.8 85s
20762 9185 236.36735 65 243 238.00000 235.98980 0.84% 79.7 94s
20767 9188 236.47899 89 73 238.00000 235.98980 0.84% 79.6 95s
Cutting planes:
Gomory: 460
Implied bound: 119
MIR: 1017
StrongCG: 383
Flow cover: 41
Zero half: 26
RLT: 3
Explored 20779 nodes (1663640 simplex iterations) in 95.76 seconds
Thread count was 4 (of 4 available processors)
Solution count 1: 238
Optimal solution found (tolerance 1.00e-04)
Best objective 2.380000000000e+02, best bound 2.380000000000e+02, gap 0.0000%
============ student 1 ==================================
Using license file C:\Users\sedon\gurobi.lic
Set parameter LogFile to value gurobi.log
Academic license - for non-commercial use only
Gurobi Optimizer version 9.0.3 build v9.0.3rc0 (win64)
Copyright (c) 2020, Gurobi Optimization, LLC
Read MPS format model from file .\CSC.mps
Reading time = 0.01 seconds
cutting-stock: 603 rows, 2400 columns, 4200 nonzeros
Optimize a model with 603 rows, 2400 columns and 4200 nonzeros
Model fingerprint: 0x1d6d7bfe
Variable types: 0 continuous, 2400 integer (600 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+01]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [2e+02, 3e+02]
Presolve time: 0.01s
Presolved: 603 rows, 2400 columns, 4200 nonzeros
Variable types: 0 continuous, 2400 integer (600 binary)
Found heuristic solution: objective 238.0000000
Root relaxation: objective 2.200000e+02, 981 iterations, 0.01 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 220.00000 0 216 238.00000 220.00000 7.56% - 0s
0 0 220.00000 0 256 238.00000 220.00000 7.56% - 0s
0 0 220.00000 0 243 238.00000 220.00000 7.56% - 0s
0 0 220.00000 0 215 238.00000 220.00000 7.56% - 0s
0 0 220.00000 0 215 238.00000 220.00000 7.56% - 0s
0 2 220.00000 0 223 238.00000 220.00000 7.56% - 0s
Cutting planes:
Gomory: 168
Implied bound: 51
MIR: 26
StrongCG: 34
Explored 1047 nodes (53835 simplex iterations) in 2.58 seconds
Thread count was 4 (of 4 available processors)
Solution count 1: 238
Optimal solution found (tolerance 1.00e-04)
Best objective 2.380000000000e+02, best bound 2.380000000000e+02, gap 0.0000%
================== student 2 =================================
Using license file /home/stefano/.gurobi/gurobi.lic
Set parameter LogFile to value gurobi.log
Academic license - for non-commercial use only
Gurobi Optimizer version 9.0.3 build v9.0.3rc0 (linux64)
Copyright (c) 2020, Gurobi Optimization, LLC
Read MPS format model from file CSC.mps
Reading time = 0.00 seconds
cutting-stock: 603 rows, 2400 columns, 4200 nonzeros
Optimize a model with 603 rows, 2400 columns and 4200 nonzeros
Model fingerprint: 0x1d6d7bfe
Variable types: 0 continuous, 2400 integer (600 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+01]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [2e+02, 2e+02]
Presolve time: 0.00s
Presolved: 603 rows, 2400 columns, 4200 nonzeros
Variable types: 0 continuous, 2400 integer (600 binary)
Found heuristic solution: objective 238.0000000
Root relaxation: objective 2.200000e+02, 1019 iterations, 0.01 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 220.00000 0 217 238.00000 220.00000 7.56% - 0s
0 0 220.00000 0 273 238.00000 220.00000 7.56% - 0s
0 0 220.00000 0 244 238.00000 220.00000 7.56% - 0s
0 0 220.00000 0 216 238.00000 220.00000 7.56% - 0s
0 0 220.00000 0 216 238.00000 220.00000 7.56% - 0s
0 2 220.00000 0 223 238.00000 220.00000 7.56% - 0s
Cutting planes:
Gomory: 164
Implied bound: 49
MIR: 26
StrongCG: 34
Explored 1071 nodes (66073 simplex iterations) in 3.86 seconds
Thread count was 8 (of 8 available processors)
Solution count 1: 238
Optimal solution found (tolerance 1.00e-04)
Best objective 2.380000000000e+02, best bound 2.380000000000e+02, gap 0.0000%
-
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?. -
-
-
Gurobi is only deterministic with respect to solving the same model on the same computer with the same parameters. Even changing the order of variables/constraints can lead to a different solution path. While it is unfortunate that the model takes so much longer to solve on your PC, this difference in solve time can likely be attributed to performance variability. There are much more extreme cases of performance variability, where (for example) Gurobi happens to run a key heuristic routine at the root node on one machine, resulting in a near-optimal incumbent solution very early in the solving process. However, this heuristic never runs on another machine, and the solver spends hours and hours working through a huge branch-and-bound tree. You can read more about this here.
What happens if you solve the model with different values of the Seed parameter? Changing the Seed parameter changes Gurobi's solution path, allowing you to see how path changes can affect the solve time. Restarting your machine and re-installing Gurobi shouldn't change the solution path, since the Gurobi library and machine environment remain the same.
I see you have a support ticket open about this issue, so we'll keep you updated there.
0 -
Post is closed for comments.
Comments
2 comments