I was wondering what the difference is between the integrality gap (i.e. best known solution in relation to the LP relaxation) and the gap from the MIP solver from Gurobi, for example. As I understand it, they are not the same, since a MIP, for example, can often never reach the value of the LP relaxation and therefore a gap of 0.00% can never be achieved, can it?
5
-
1$\begingroup$ In the MIP, the gap comes from the difference between LB and UB. In each iteration of the B&B tree both are updated and in many cases reach the same value, actually with an acceptable tolerance. $\endgroup$– A.OmidiCommented Jun 18 at 8:41
-
$\begingroup$ Thanks, that means the lower bound is not the value from the LP-Relaxation? $\endgroup$– ornewbieCommented Jun 18 at 8:50
-
1$\begingroup$ The initial LB comes from the LP relaxation. This LB may be updated in each iteration of the B&B tree further. This is what you can see as the best bound in the MIP logs. $\endgroup$– A.OmidiCommented Jun 18 at 9:11
-
1$\begingroup$ @A.Omidi to be more accurate, the initial LB comes from the LP relaxation of the presolved model, which might be better than the LP relaxation of the original model if some integer variable domains have change $\endgroup$– fontanfCommented Jun 18 at 16:00
-
$\begingroup$ Dear @fontanf, thank you so much for pointing this out. 🙏 $\endgroup$– A.OmidiCommented Jun 18 at 19:01
Add a comment
|