Statistical optimum estimation techniques for combinatorial optimization problems: a review and critique

Over the last several decades researchers have addressed the use of statistical techniques to estimate the optimal values of difficult optimization problems. These efforts have been developed in different communities with a wide range of different applications in mind. In this paper we review the theory and applications of these approaches and discuss their strengths and weaknesses. We conclude the paper with a discussion of issues to consider when using these methods in computational experiments, and suggest directions for future research.