Unified Approach to Statistical Quality Assessment in Heuristic Combinatorial Optimization

摘要

Since the introduction of mathematical programming it has been all too easy to identify real-world problems that could be formulated as math programs but could not be solved to a provable optimum within a reasonable amount of time. As computing power continues to increase, so too does the size of the mathematical programs to be solved. This situation has given rise to a multitude of heuristic solution techniques that seek to provide good approximate solutions within a reasonable amount of time. Designers and users of heuristic solution techniques would like to assess the quality of their heuristics, where heuristic quality is defined in terms of the characteristics of the solutions returned by the heuristic, often emphasizing the objective function values. Fixed bounds on worst case performance are available for some heuristics, but in many cases heuristic-quality assessment approaches must take a sampling perspective and apply statistical tools to derive their assessment. Although many authors have proposed statistical methods for assessing heuristic quality, there has not been a foundation for a single unified approach or a framework for comparison of the distinct approaches to heuristic-quality assessment. The primary contribution of this research is that it presents a unifying probability modeling framework that applies whenever randomized heuristic solution techniques are applied to instances of combinatorial optimization problems. With this probability model in hand, we can better understand the relative strengths and weaknesses of the existing statistical approaches to assessing heuristic quality in combinatorial optimization. Moreover, the probability model suggests new avenues for the development of heuristic quality assessment approaches, and we present empirical results from initial applications.