Assessing the quality of heuristic solutions to combinatorial optimization problems (COP) is very important problem. In my view, this problem is a million time more important than finding a heuristic solution. Therefore I want to share my point of view on this questrion. So you try to solve a COP by using a heuristic algorithm A for an input data D. Let you got a solution A(D) and you are interested to know about quality of A(D) to an optimal solution OPT(D), i.e. you can use a metric q = 100% * (A(D) - OPT(D)) / OPT(D). But OPT(D) is not known, because of you can use a metric p = 100% * (A(D) - LB(D)) / LB(D), where LB(D) is a Lower Bound of your objective function, LB(D)

@Gennady. Indeed, it is a very important problem. The approach of deterministic bounds that you bring up is one strategy. We compared deterministic bounds to statistical bounds in the paper and found generally that statistical bounds provided a much tighter bounds than deterministic for the COP:s we considered.

Dear Kenneth,

I try to understand one thing: Are your statistical bounds to be proved if optimal solution is not known before? In my opinion, any Lower Bound must be rigorously proved without using any statistics. I don't know that your statistical bounds have this property. Well, assume I want to solve your COP model and found a solution A(D) for concrete data D, where A is my heuristic algorithm. Then I want to ask you: Can you evaluate A(D) using your statistical bounds at the moment?

My answer to the question is yes. Say that b0 is the unknown optimum. We have a known heuristic solution b1 where b1>=b0. Deterministic bounds would be b1 as the upper bound and a1, say, as the lower bound. In this case we know by certainty that the unknown optimum b0 is in the interval (a1,b1). Statistical bounds also provide a lower bound (or rather confidence limit) s1, say. In this case we don not know by certainty that b0 is in the interval (s1,b1), but with a certain degree of confidence. In the experiments we conducted the confidence level was close to one, 0.997. Hence, the statistical bounds provide an interval almost certainly containing b0.

The question is: am I willing to trade certainty to almost certain if I in return get drastically shorter intervals? It depends of course on the context. But in many cases the answer  would be yes to the question.

Thanks for your inputs!  

Dear Kenneth,

Unfortunately, your answer did not satisfy me completely. I asked about Lower Bound to be proven rigorously, i.e. LB(D) by definition, must be a value with confidence level = 1 , otherwise it will not be named as Lower Bound. Well, you got Lower Bound s1 (as you say) with confidence level = p . Assume that b1 = s1. Then you claim that you produced an optimal solition with confidence level = p: the more p the more b1 can be consedered as optimal solution. But such statement can not be accepted seriously. Please clarify your thought.

Thank you in advance.

First, assume a solution b1. Irrespective of whether putting deterministic or statistical bounds to b0 (the optimum), we will not know the value of b0. For deterministic bounds we only know that b0 is in the interval (a1,b1) (a1=LB(D) in your notations). If and only if a1=b1, we know that our solution b1 equals the optimum b0. Now, your point seems to be that we should put effort in enhancing LB(D). I agree, and from your publications it is clear that you are contributing in this regard.

As for the statistical bounds, I find the assumption of b1=s1 impermissable. It is a degenerated situation when there is no uncertainty about b0, in which case p=1.

The confidence level refers to how likely it is that the interval (s1,b1) contains b0. Thus it is a statement of the confidence about the interval, not about b1. 

Continued. So what do you prefer? We have a solution b1 and the two lower bounds a1 and s1. abs(b1-a1) >> abs(b1-s1). Do you prefer to be certain that b0 is somewhere between b1 and a1 or do you prefer to be almost certain that b0 is between b1 and s1?

I prefer "to be certain that b0 is somewhere between b1 and a1" with confidence level = 1 and even don't consider "almost certain that b0 is between b1 and s1" with any confidence level < 1 . This is not a case where the theory of probability. As example, you can image the following statement: "This theorem was proven with confidence level = 0,999" . As to me, my answer would be NO. Here we can consider only

a single case: "This theorem was proven with confidence level = 1". For all other confidence level < 1 theorem not be considered to be proven.  Well, you can say a phrase: "I found solution with confidence level = 0.999". I think that answer would be NO. Thus, my resume is the following: we must consider seriously only reliable events (a1) with confidence level = 1. To as s1 > a1, this metric can be consedered as any "recomendation". To as me, in case of b1 = s1 I will not interrupt the search of finding b0 by claiming a phrase: "I found an optimal solution b0".

In conclusion, I again want to remind about great importance of finding quality a1 to evaluate a heuristic solution b1 at the moment.