An analytical evaluation of optimal solution value estimation procedures

Robert L. Nydick and Howard J. Weiss

Naval Research Logistics (NRL), 1994, vol. 41, issue 2, 189-202

Abstract: 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, we 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 we provide a framework to analytically evaluate a class of optimal solution value estimators. We 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, we show how to compute the estimation errors for distributions other than uniform given a specific sample size. We 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, our 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. © 1994 John Wiley & Sons, Inc.

Date: 1994
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199403)41:23.0.CO;2-9

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:41:y:1994:i:2:p:189-202

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().