How is the optimality gap, or MIP gap, calculated?

The optimality gap, also known as the MIP gap (mixed-integer programming gap), is a measure of how close a solution obtained by the solver is to the optimal solution, in the worst case. It is calculated as the difference between the best-known feasible solution (incumbent) and the best bound on the objective function, expressed as a percentage of the best-known feasible solution. The formula for calculating the MIP gap is given below.

Optimality gap = |best objective - best bound| / |best objective|
               = absolute gap / |best objective|

Here

• best objective refers to the objective value of the best-known feasible solution, and
• best bound represents the objective value of the relaxed problem, which is the lower bound for minimization problems and the upper bound for maximization problems.

The MIP gap indicates the worst-case deviation of the current solution from the true optimal solution, with a lower MIP gap representing a solution closer to optimality. The specific values for best objective, best bound, and absolute gap can all be found in the web interface. You can also use the optimality gap as a criterion for when to stop the solver. See these articles for more information on specifying stopping criteria.

• Basic solver parameters (stopping criteria)
• How to change and view the solver parameters

Note that if the best objective is zero, the optimality gap is undefined due to dividing by zero, but will be displayed as zero.

Also note that if the problem is purely linear, meaning it does not have any integer constraints, or a MIP problem is solved in pre-solve, then the optimality gap will be zero and the values for the best objective nor best bound will be shown. It is automatically known in these cases that best bound and best objective are equal to the optimal objective function value.