This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Hall, N. G. Articles by Posner, M. E. Search for Related Content

Performance Prediction and Preselection for Optimization and Heuristic Solution Procedures

Fisher College of Business, The Ohio State University, Columbus, Ohio 43210
Integrated Systems Engineering, The Ohio State University, Columbus, Ohio 43210
hall.33{at}osu.edu
posner.1{at}osu.edu

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.

Subject classifications: computational testing; prediction of solution procedure performance; choice of solution procedure; statistical analysis; programming; integer; algorithms; heuristics; analysis of algorithms; suboptimal algorithms; statistics; data analysis.
History: Received October 2004; revision received September 2005; accepted March 2006.