Performance Prediction and Preselection for Optimization and Heuristic Solution Procedures

Nicholas G. Hall () and Marc E. Posner ()
Additional contact information
Nicholas G. Hall: Fisher College of Business, The Ohio State University, Columbus, Ohio 43210
Marc E. Posner: Integrated Systems Engineering, The Ohio State University, Columbus, Ohio 43210

Operations Research, 2007, vol. 55, issue 4, 703-716

Abstract: 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.

Keywords: 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 (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1070.0398 (application/pdf)

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:inm:oropre:v:55:y:2007:i:4:p:703-716

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().