4
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your feedback. I agree it seems very far fetched to be able to come up with a probabilistic statement given the nature of branch-and-bound procedure. That said, I'm curious to know how to estimate these probabilities experimentally, as you pointed out. Any suggestions? $\endgroup$ – user2512443 May 15 at 0:00
  • $\begingroup$ I just meant, solve the model a bunch of times for a bunch of randomly generated instances, and empirically estimate the distribution of the gaps. But this seems prohibitively computationally intensive. $\endgroup$ – LarrySnyder610 May 15 at 0:36
  • 2
    $\begingroup$ 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. $\endgroup$ – rcorywright May 15 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.