Performance Prediction and Preselection for Optimization and Heuristic Solution Procedures

摘要

The operations research literature contains numerous studies on the design and application of optimization and heuristic solution procedures. These studies identify a particular optimization problem, suggest a general solution procedure, and then customize that procedure to improve its efficiency and/or accuracy. In contrast, this paper shows how to use existing solution procedures more effectively. We develop a methodology for predicting the relative performance of alternative procedures, using easily computed problem characteristics. This methodology enables us, for any given data set, to preselect a solution procedure. We apply this preselection methodology to the 0-1 knapsack problem for which two successful optimization procedures, dynamic programming and branch-and-search, are available. Extensive computational testing indicates that substantial savings in average computation time are achieved. The benefits of our work include faster and cheaper identification of effective solution procedures, as well as an improved understanding of the relationship between problem characteristics and the performance of various procedures. Our methodology can be applied to many optimization problems to develop easily implemented guidelines for selecting appropriate solution procedures.