# Probabilistic interpretation of optimality gap in Integer Program

Suppose I have an integer program model in the form of a minimization. I noticed that Gurobi (my solver) often finds a very good upper bound (i.e., feasible solution) whereas it takes a significant time to improve the lower bound to reduce the optimality gap.

Here is my question. Is there a way to obtain a probabilistic statement about the optimality? For instance say

$$prob\{f^u - f^\star > \epsilon\} \le \gamma$$

where $$f^u$$ is an upper bound and $$f^{\star}$$ is the global objective value.

Similarly, an inequality in this form is also desirable:

$$prob\{f^u - f^{\ell} > \epsilon\} \le \gamma$$

where $$f^{\ell}$$ is the lower bound.

Any thoughts or suggestions will greatly be appreciated!

• I agree with this answer in general. One exception: if Gurobi generates a feasible solution from a randomized rounding method (or Gurobi's solution is better than a solution which you independently generate from a randomized rounding method), then you can sometimes write down bounds on $\epsilon$ and $\gamma$. For instance, using the probability distribution which arises in the proof of Goemans-Willliamson rounding, you should be able to do this. – rcorywright May 15 at 3:48