What exactly is the optimality-gap or what does it say in integer linear programming?

Question

I am working since a few months with gurobi and did figure out, that the gap says how far a feasible solutions is away from the optimal solution. However, what does say it exactly?

The gurobi docs says it depends on the upper and lower objective bound. I figured out, that this depends to duality.

As I did understand this topic: The lower bound descripes an objective value for the lowest values of the decision variables that is still feasible. The upper bound does descripe the highest values for feasible objective value. So the gap for a feasible solution descripes the distances between those bounds. However, which one do the solver exactly know and which one is a solution the solver founds during the branch-and-bound process?

Answer 1

In a minimization problem, the lower bound will be a value below which the objective value cannot go. The upper bound will be the objective value of the best solution found so far. The lower bound is found by solving a relaxation of the subproblem at each surviving node of the search tree and taking the smallest objective value of any of those nodes. So at any given point you know that the upper bound is attainable (because it comes from the current incumbent solution) and that you may or may not be able to improve on it, and you know that the optimal objective cannot be better than the lower bound (best relaxed objective value of any node). The upper bound improves each time you find a new incumbent, and the lower bound improves as nodes are pruned from the search tree.

For a maximization problem, the reverse occurs. The lower bound is the incumbent objective value and the upper bound is the largest (relaxed) objective value at any live node.