Calculation of upper bound, lower bound and gap

[Anne Lise Antomarchi]

Hello,

I am using Gurobi to solve a MIP. It is a problem of maximization. 

I would like to know, how are calculated the upper bound and the lower bound.

The gap is calculated from these bounds, these bounds change in relation to iteration. So, how to interpret it ? 

Thank you,

Anne-Lise

[Robert Luce]

Hello Anne-Lise,

for a maximization problem, the lower bound is the objective function value corresponding to the best integer feasible solution (the "incumbent").  The upper bound is the objective function value of an LP relaxation of the problem, proving that no integer feasible solution of larger objective value than this value can exist.  Hence the difference of these two bounds can serve as a measure of optimality.

A concise summary of the branch-and-bound mechanics that is based on these bounds is given here:

http://www.gurobi.com/resources/getting-started/mip-basics

Best,

Robert