Log reporting wrong bounds in multiobjective environment
回答済みHey there,
I ran a model that first minimizes the number of persons needed for a logistical process and then using setObjectiveN with lower priority to distribute the workload equally among those. The log reported an optimal solution of 18, whereas from the variables I get 22.
I did some tests and inserted a callback to report back the solution value from the affected variables as well as the bound:
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 13.40627 0 1726 - 13.40627 - - 9s
Callback Solution: 48.0
Callback Bound: 14.0
H 0 0 44.0000000 13.40627 69.5% - 10s
0 0 13.70583 0 1512 44.00000 13.70583 68.9% - 25s
0 0 15.47150 0 2174 44.00000 15.47150 64.8% - 27s
Callback Solution: 40.0
Callback Bound: 16.0
H 0 0 36.0000000 15.66518 56.5% - 32s
0 0 15.82554 0 1554 36.00000 15.82554 56.0% - 35s
0 0 16.04598 0 1210 36.00000 16.04598 55.4% - 38s
0 0 16.04598 0 1214 36.00000 16.04598 55.4% - 38s
Callback Solution: 39.0
Callback Bound: 17.0
H 0 0 35.0000000 16.42692 53.1% - 46s
Callback Solution: 25.0
Callback Bound: 17.0
H 0 0 21.0000000 16.42692 21.8% - 46s
Callback Solution: 22.0
Callback Bound: 17.0
H 0 0 18.0000000 16.42692 8.74% - 46s
0 0 16.42692 0 1629 18.00000 16.42692 8.74% - 46s
Cutting planes:
Gomory: 138
Implied bound: 1
MIR: 36
StrongCG: 2
Flow cover: 94
Zero half: 77
RLT: 449
Relax-and-lift: 1
BQP: 858
Explored 1 nodes (51384 simplex iterations) in 46.64 seconds (60.48 work units)
Thread count was 32 (of 144 available processors)
Solution count 5: 18 21 35 ... 44
Optimal solution found (tolerance 2.10e-01)
Best objective 1.800000000000e+01, best bound 1.700000000000e+01, gap 5.5556%
When running only the first objective in a single objective environment the log reports the correct values:
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 17.40627 0 1732 - 17.40627 - - 8s
0 0 17.49180 0 1856 - 17.49180 - - 19s
0 0 19.42621 0 2177 - 19.42621 - - 22s
Callback Solution: 45.0
Callback Bound: 20.0
H 0 0 45.0000000 19.64511 56.3% - 27s
0 0 19.73574 0 1873 45.00000 19.73574 56.1% - 28s
0 0 20.04598 0 1259 45.00000 20.04598 55.5% - 31s
0 0 20.04598 0 1251 45.00000 20.04598 55.5% - 31s
0 0 20.42691 0 1537 45.00000 20.42691 54.6% - 34s
Callback Solution: 43.0
Callback Bound: 21.0
H 0 0 43.0000000 20.42691 52.5% - 34s
0 0 20.42691 0 1430 43.00000 20.42691 52.5% - 34s
0 0 20.77883 0 996 43.00000 20.77883 51.7% - 36s
0 0 20.82867 0 908 43.00000 20.82867 51.6% - 37s
0 0 20.82874 0 921 43.00000 20.82874 51.6% - 37s
0 0 20.88593 0 1005 43.00000 20.88593 51.4% - 38s
Callback Solution: 41.0
Callback Bound: 21.0
H 0 0 41.0000000 20.88593 49.1% - 38s
Callback Solution: 37.0
Callback Bound: 21.0
H 0 0 37.0000000 20.88593 43.6% - 38s
0 0 20.88597 0 996 37.00000 20.88597 43.6% - 38s
0 0 20.91788 0 1111 37.00000 20.91788 43.5% - 40s
Callback Solution: 35.0
Callback Bound: 21.0
H 0 0 35.0000000 20.91788 40.2% - 40s
Callback Solution: 34.0
Callback Bound: 21.0
H 0 0 34.0000000 20.91788 38.5% - 40s
0 0 20.91789 0 1055 34.00000 20.91789 38.5% - 40s
0 0 20.93827 0 1147 34.00000 20.93827 38.4% - 41s
0 0 20.93827 0 2021 34.00000 20.93827 38.4% - 44s
0 0 21.00000 0 1742 34.00000 21.00000 38.2% - 44s
Callback Solution: 30.0
Callback Bound: 21.0
H 0 0 30.0000000 21.00000 30.0% - 45s
0 0 21.00174 0 1308 30.00000 21.00174 30.0% - 49s
Callback Solution: 28.0
Callback Bound: 22.0
H 0 0 28.0000000 21.00174 25.0% - 49s
0 0 21.01598 0 1419 28.00000 21.01598 24.9% - 56s
Callback Solution: 27.0
Callback Bound: 22.0
H 0 0 27.0000000 21.01598 22.2% - 67s
Callback Solution: 26.0
Callback Bound: 22.0
H 0 0 26.0000000 21.01598 19.2% - 67s
Callback Solution: 23.0
Callback Bound: 22.0
H 0 0 23.0000000 21.01598 8.63% - 67s
Callback Solution: 22.0
Callback Bound: 22.0
H 0 0 22.0000000 21.01598 4.47% - 67s
0 0 21.02087 0 1565 22.00000 21.02087 4.45% - 67s
Cutting planes:
Gomory: 31
Cover: 2
Implied bound: 2
Clique: 2
MIR: 563
StrongCG: 3
Flow cover: 228
Zero half: 64
RLT: 698
BQP: 2167
Explored 1 nodes (80035 simplex iterations) in 67.44 seconds (92.33 work units)
Thread count was 32 (of 144 available processors)
Solution count 10: 22 23 26 ... 41
It seems that both bounds are shifted by value 4 (maybe determined by the presolver?) in the multi-objective case, which 1) makes interpreting solutions when debugging the log harder and 2) the MIPGap determination criterion seems to be based on the shifted values (and presumably so are the relative tolerances if used) as can be seen in the first log. The second to last solution actually has incumbent/BestBd of 25 to 20.42692 => 16% and therefore below the termination criterion of 21%.
This only happens in Gurobi 10.0.0, I have tested the same model with 9.5.2 and both values are reported correctly. Is this expected behavior or a bug?
-
正式なコメント
Hi Philip,
Thank you for reporting this. The behavior you observe is related to a bug that is present in Gurobi 10.0.0 and that will be fixed in the next release. The article Why does Gurobi 10.0.0 report an incorrect objective value for my multi-objective problem? explains the causes of this bug more in detail and gives two workarounds.
Let us know if you have further questions.
Elisabeth
サインインしてコメントを残してください。
コメント
1件のコメント