An analytical evaluation of optimal solution value estimation procedures

The estimation of optimal solution values for large-scale optimization problems is studied. Optimal solution value estimators provide information about the deviation between the optimal solution and the heuristic solution. Some estimation techniques combine heuristic solutions with randomly generated solutions. In particular, the authors examine a class of jacknife-based estimators which incorporate any heuristic solution value with the two best randomly generated solution values. The primary contribution of this article is that a framework is provided to analytically evaluate a class of optimal solution value estimators. The authors present closed-form results on the relationship of heuristic performance, sample size, and the estimation errors for the case where the feasible solutions are uniformly distributed. In addition, they show how to compute the estimation errors for distributions other than uniform given a specific sample size. The authors use a triangular and an exponential distribution as examples of other distributions. A second major contribution of this article is that, to a large extent, the present analytical results confirm previous computational results. In particular, the best estimator depends on how good the heuristic is, but seems to be independent of the underlying distribution of solution values. Furthermore, there is essentially an inverse relationship between the heuristic performance and the performance of any estimator.