Performance prediction and Preselection for optimization and heuristic solution procedures
成果类型：
Article
署名作者：
Hall, Nicholas G.; Posner, Marc E.
署名单位：
University System of Ohio; Ohio State University; University System of Ohio; Ohio State University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1070.0398
发表日期：
2007
页码：
703-716
关键词：
摘要：
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.