Performance Prediction and Preselection for Optimization and Heuristic Solution Procedures
- 1 August 2007
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 55 (4), 703-716
- https://doi.org/10.1287/opre.1070.0398
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
This publication has 29 references indexed in Scilit:
- Generating Experimental Data for Computational Testing with Machine Scheduling ApplicationsOperations Research, 2001
- On the classification of NP-complete problems in terms of their correlation coefficientDiscrete Applied Mathematics, 2000
- Autocorrelation coefficient for the graph bipartitioning problemTheoretical Computer Science, 1998
- Neural NetworksPublished by Springer Science and Business Media LLC ,1991
- The Shifting Bottleneck Procedure for Job Shop SchedulingManagement Science, 1988
- A linear-time approximation algorithm for the weighted vertex cover problemJournal of Algorithms, 1981
- An Algorithm for Large Zero-One Knapsack ProblemsOperations Research, 1980
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979
- The Bottleneck Traveling Salesman ProblemJournal of the ACM, 1978
- A Computing Procedure for Quantification TheoryJournal of the ACM, 1960