Confusion about MILP log: "best objective" not part of solutions, gap doesn't match

Hello,

I try to minimze an MILP problem of which I know that the optimal solution is 0. I formulated the problem in Matlab 2020b using the latest version of YALMIP as interface and Gurobi v9.1.1. However, the termination doesn't seem to work and the log is inconsistent. Below, I'm reporting some logs and my observations

1. I was puzzled that the solver doesn't report a gap and hence doesn't terminate although an optimal heuristic objective was found

Root relaxation: objective 0.000000e+00, 18016 iterations, 4.16 seconds
Total elapsed time = 11.89s

Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

0 0 0.00000 0 10 - 0.00000 - - 12s
H 0 0 0.0000000 0.00000 - - 14s
0 0 0.00000 0 7 0.00000 0.00000 - - 21s
[shortened]


120067 18163 0.00000 293 3 0.00000 0.00000 - 16.9 1686s

Interrupt request received
120683 18175 - 289 0.00000 0.00000 - 16.9 1691s

Explored 121075 nodes (2087179 simplex iterations) in 1691.73 seconds
Thread count was 4 (of 32 available processors)

Solution count 1: 1.39698e-09 
No other solutions better than 5.33873e-10

Solve interrupted
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%

Already noticeable: the best objective is not part of the solutions presented with "Solution count" which I attributed to the solve interruption.
Regarding the gap: my assumption was that the best bound is perfect 0, i.e. the gap can only be 100% or 0% (taking gap = (incumbent-bestBound)/incumbent).

2. To avoid the 0% gap problem, I added a constant offset of 1e-5 to the objective function. Gurobi could solve the problem as expected, but the log is still inconstitent

Root relaxation: objective 9.998679e-06, 54585 iterations, 14.42 seconds

Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

* 0 0 0 0.0000100 0.00001 0.00% - 18s

Explored 0 nodes (54585 simplex iterations) in 18.21 seconds
Thread count was 4 (of 32 available processors)

Solution count 1: 9.98937e-06

Optimal solution found (tolerance 5.00e-04)
Warning: max constraint violation (1.8059e-04) exceeds tolerance
Best objective 1.000000000000e-05, best bound 9.989365935326e-06, gap 0.1063%
Optimization completed in 25.35 s

Again, the best objective reported (1.00e-5) doesn't agree with the solution reported (9.99e-6). In addition, the final gap reported (0.1063%) doesn't match the 0.00% gap shown in the B&C log.

At this point, I'm not sure if there is a fundamental problem or if I'm just misreading the logs. Hope somebody can help here.

Best,
Lukas

正式なコメント

Simranjit Kaur

Gurobi Staff

2024年12月06日 00:35

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?.

Jaromił Najman

2021年03月03日 08:26

Hi Lukas,

Could you share the Problem statistics reported in the first ~30 lines of an optimization run? Is it possible for you to share an instance of the problem to make an investigation easier? You can share files as described in Posting to the Community Forum.

Best regards,
Jaromił

Confusion about MILP log: "best objective" not part of solutions, gap doesn't match

コメント

お探しのものを見つけられませんでしたか？