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!
Unfortunately, no. There is really nothing else you can say other than that the optimal solution is between the two bounds.
Presumably you could estimate these probabilities experimentally, but I assume that is not what you’re asking.