Skip to main content
SpringerLink
Log in

Experimental Evaluation of Heuristic Optimization Algorithms: A Tutorial

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

Heuristic optimization algorithms seek good feasible solutions to optimization problems in circumstances where the complexities of the problem or the limited time available for solution do not allow exact solution. Although worst case and probabilistic analysis of algorithms have produced insight on some classic models, most of the heuristics developed for large optimization problem must be evaluated empirically—by applying procedures to a collection of specific instances and comparing the observed solution quality and computational burden.

This paper focuses on the methodological issues that must be confronted by researchers undertaking such experimental evaluations of heuristics, including experimental design, sources of test instances, measures of algorithmic performance, analysis of results, and presentation in papers and talks. The questions are difficult, and there are no clear right answers. We seek only to highlight the main issues, present alternative ways of addressing them under different circumstances, and caution about pitfalls to avoid.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Computational Testing of Algorithms.” INFORMS Journal on Computing 8, 318–330.

    Google Scholar 

  • Arthur, J.L. and J.O. Frendewey. (1988). “Generating Travelling Salesman Problems with Known Optimal Tour Length.” Journal of the Operational Research Society 39, 153–159.

    Google Scholar 

  • Baker, K.R. (1997). “Heuristic Procedures for Scheduling Job Families with Setups and Due Dates.” Working paper, Amos Tuck School of Business Administration, Dartmouth College.

  • Baker, K.R. and M.J. Magazine. (1997). “Minimizing Maximum Lateness with Job Families.” Working paper, Amos Tuck School of Business Administration, Dartmouth College.

  • Barr, R.S., B.L. Golden, J.P. Kelly, M.G.C. Resende, and W.R. Stewart. (1995). “Designing and Reporting on Computational Experiments with Heuristic Methods.” Journal of Heuristics 1, 9–32.

    Google Scholar 

  • Barr, R.S. and B.L. Hickman. (1993). “Reporting Computational Experiments with Parallel Algorithms: Issues, Measures and Experts Opinions.” ORSA Journal on Computing 5, 2–18.

    Google Scholar 

  • Bixby, B. and G. Reinelt. (1990). TSPLIB, Software Library, Rice University, Houston, Texas.

    Google Scholar 

  • Boender, C.G.E., A.H.G. Rinnooy Kan, L. Stougie, and G.T. Timmer. (1982). “A Stochastic Method for Global Optimization.” Mathematical Programming 22, 125–140.

    Google Scholar 

  • Burkard, R.E. and U. Fincke. (1983). “The Asymptotic Probabilistc Behaviour of Quadratic Sum Assignment Problems.” Z. Opns. Res. 27, 73–81.

    Google Scholar 

  • Coffman, E.G., G.S. Lueker, and A.H.G. Rinnooy Kan. (1988). “Asymptotic Methods in the Probablistic Analysis of Sequencing and Packing Heuristics.” Management Science 34, 266–290.

    Google Scholar 

  • Conover, W.J. (1980). Practical Nonparametric Statistics. New York: John Wiley.

    Google Scholar 

  • Crawford, J.M. and L.D. Auton. (1983). “Experimental Results on the Crossover Point in Satisfiability Problems.” In Proceedings of the Eleventh National Conference on Artificial Intelligence AAAI93. pp. 21–27.

    Google Scholar 

  • Crowder, H.P., R.S. Dembo, and J.M. Mulvey. (1979). “On Reporting Computational Experiments with Mathematical Software.” ACM Transactions on Mathematical Software 5, 193–203.

    Google Scholar 

  • Dannenbring, D. (1977). “Estimating Optimal Solutions for Large Combinatorial Problems.” Management Science 23, 1273–1283.

    Google Scholar 

  • Demirkol, E., S.V. Mehta, and R. Uzsoy. (1998). “Benchmarks for Shop Scheduling Problems.” European Journal of Operational Research 109, 137–141.

    Google Scholar 

  • Derigs, U. (1985). “Using Confidence Limits for the Global Optimal in Combinatorial Optimization.” Operations Research 33, 1024–1049.

    Google Scholar 

  • Fargher, H.E. and R.A. Smith. (1994). “Planning in a Flexible Semiconductor Manufacturing Environment.” In M. Zweben and M. Fox (eds.), Intelligent Scheduling. Morgan Kaufman.

  • Fisher, H. and G.L. Thompson. (1963). “Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules.” In J.F. Muth and G.L. Thompson (eds.), Industrial Scheduling. New Jersey: Prentice-Hall, Englewood Cliffs.

    Google Scholar 

  • Fisher, R. and L. Tippett. (1928). “Limiting Forms of the Frequency Distribution of the Largest or Smallest Member of a Sample.” Proceedings of the Cambridge Philosophical Society 24, 180–190.

    Google Scholar 

  • Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman.

    Google Scholar 

  • Garfinkel, R.S. and K.C. Gilbert. (1978). “The Bottleneck Traveling Salesman Problem: Algorithms and Probabilistic Analysis.” Journal of the ACM 25, 435–448.

    Google Scholar 

  • Ghashghai, E. and R.L. Rardin. (1998). “Using a Hybrid of Exact and Genetic Algorithms to Design Survivable Networks.” Working paper, School of Industrial Engineering, Purdue University.

  • Golden, B.L. (1977). “A Statistical Approach to the TSP.” Networks 7, 209–225.

    Google Scholar 

  • Golden, B.L. (1978). “Point Estimation of a Global Optimum for Large Combinatorial Problems.” Communications in Statistics B7, 361–367.

    Google Scholar 

  • Golden, B.L. and F.B. Alt. (1979). “Interval Estimation of a Global Optimum for Large Combinatorial Problems.” Naval Research Logistics Quarterly 26, 69–77.

    Google Scholar 

  • Golden, B.L., A.A. Assad, E.A. Wasil, and E. Baker. (1986). “Experimentation in Optimization.” European Journal of Operational Research 27, 1–16 (1986).

    Google Scholar 

  • Golden, B.L. and W.R. Stewart. (1985). “Empirical Evaluation of Heuristics.” In E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys (eds.), The Traveling Salesman problem: A Guided Tour of Combinatorial Optimization. New York: John Wiley.

    Google Scholar 

  • Goldsman, D. and B.L. Nelson. (1999). “Comparing Systems via Simulation.” In J. Banks (ed.), Handbook of Stimulation. New York: John Wiley.

    Google Scholar 

  • Graham, R.L. (1969). “Bounds on Multiprocessor Timing Anomalies.” SIAM Journal of Applied Mathematics 17, 416–429.

    Google Scholar 

  • Greenberg, H.J. (1990). “Computational Testing: Why, How and How Much.” ORSA Journal on Computing 2, 94–97.

    Google Scholar 

  • Grötchel, M. and M.W. Padberg (1979). “On the Symmetric Traveling Salesman Problem I: Inequalities.” Mathematical Programming 16.

  • Grötchel, M. and M.W. Padberg. (1985). “Polyhedral Aspects of the Traveling Salesman Problem I: Theory.” In E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys (eds.), The Traveling Salesman problem: A Guided Tour of Combinatorial Optimization. New York: John Wiley.

    Google Scholar 

  • Hall, N.G. and M. Posner. (1996). “Generating Experimental Data for Scheduling Problems.” Research report, College of Business, Ohio State University.

  • Hariri, A.M.A. and C.N. Potts. (1997). “Single Machine Scheduling with Batch Set-up Times to Minimize Maximum Lateness.” Annals of Operations Research 70, 75–92.

    Google Scholar 

  • Hill, R.R. and C.H. Reilly. (1996a). “Multivariate Composite Distributions for Co-efficients in Synthetic Optimization Problems.” Research report, Department of Industrial, Welding and Systems Engineering, Ohio State University.

  • Hill, R.R. and C.H. Reilly. (1996b). “The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance.” Research report, Department of Industrial, Welding and Systems Engineering, Ohio State University.

  • Hooker, J. (1994). “Needed: An Empirical Science of Algorithms.” Operations Research 42, 201–212.

    Google Scholar 

  • Hooker, J. (1995). “Testing Heuristics: We Have It All Wrong.” Journal of Heuristics 1, 33–42.

    Google Scholar 

  • Jackson, R.H.F., P.T. Boggs, S.G. Nash, and S. Powell. (1991). “Guidelines for Reporting Results of Computational Experiments: Report of the Ad Hoc Committee.” Mathematical Programming 49, 413–425.

    Google Scholar 

  • Jones, C.V. (1996). Visualization and Optimization. Boston: Kluwer Academic Publishers. Boston.

    Google Scholar 

  • Karp, R.M. (1977). “Probabilistic Analysis of Partitioning Algorithms for the Traveling Salesman Problem in the Plane.” Mathematics of Operations Research 2, 209–224.

  • Khoury, B.N., P.M. Paradalos, and D.Z. Zhu. (1993). “A Test Problem Generator for the Steiner Problem in Graphs.” ACM Transactions on Mathematical Software 19, 509–522.

    Google Scholar 

  • Kilbridge, M.D. and L. Wester. (1996). “A Heuristic Method of Assembly Line Balancing.” Journal of Industrial Engineering 12, 394–398.

    Google Scholar 

  • King, J.R. (1980). “Machine-Component Grouping in Production Flow Analysis: An Approach Using a Rank Order Clustering Algorithm.” International Journal of Production Research 18, 213–232.

    Google Scholar 

  • Klein, S. (1975). “Monte Carlo Estimation in Complex Optimization Problems.” Ph.D. Dissertation, George Washington University, Washington, D.C.

    Google Scholar 

  • Krishnamurthy, B. (1987). “Constructing Test Cases for Partitioning Heuristics.” IEEE Transactions on Computing 36, 1112–1114.

    Google Scholar 

  • Law, A.M. and W.D. Kelton. (1991). Simulation Design and Analysis, 2nd edn. New York: McGraw-Hill, Inc.

    Google Scholar 

  • Lee, C.Y., J. Bard, M. Pinedo, and W.E. Wilhelm. (1993). “Guidelines for Reporting Computational Results in IIE Transactions.” IIE Transactions 25, 71–73.

    Google Scholar 

  • Lenstra, J.K. (1977). “Sequencing by Enumerative Methods.” Mathematical Center Tract 69, Mathematisch Centrum, Amsterdam.

    Google Scholar 

  • Lin, B.W. and R.L. Rardin. (1980). “Controlled Experimental Design for Statistical Comparison of Integer Programming Algorithms.” Management Science 25, 1258–1271.

    Google Scholar 

  • Lin, S. and B.W. Kernighan. (1973). “An Effective Heuristic Method for the Travelling Salesman Problem.” Operations Research 21, 498–516.

    Google Scholar 

  • Los, M. and C. Lardinois. (1982). “Combinatorial Programming, Satistical Optimization and the Optimal Transportation Network.” Transportation Research Board 16B, 89–124.

    Google Scholar 

  • McGeoch, C.C. (1996). “Towards an Experimental Method for Algorithm Simulation.” INFORMS Journal on Computing 8, 1–15.

    Google Scholar 

  • Mitchell, D., B. Selman, and H. Leveque. (1992). “Hard and Easy Distributions of SAT Problems.” In Proceedings of the Tenth National Conference on Artificial Intelligence AAA192. 459–465.

    Google Scholar 

  • Monma, C. and C.N. Potts. (1989). “On the Complexity of Scheduling with Batch Setup Times.” Operations Research 37, 798–804.

    Google Scholar 

  • Montgomery, D.C. (1991). Design and Analysis of Experiments, 3rd edn. New York: John Wiley.

    Google Scholar 

  • Moscato, P. and M.G. Norman. (1998). “On the Performance of Heuristics on Finite and Infinite Fractal Instances of the Euclidean Traveling Salesman Problem.” INFORMS Journal on Computing 10, 121–132.

    Google Scholar 

  • Ovacik, I.M., S. Rajagopalan, and R. Uzsoy. (2000). “Integrating Interval Estimates of Global Optima and Local Search Methods for Combinatorial Optimization Problems.” Journal of Heuristics, 6, 481–500.

    Google Scholar 

  • Ovacik, I.M. and R. Uzsoy. (1997). Decomposition Methods for Complex Factory Scheduling Problems. Boston: Kluwer Academic Publishers.

    Google Scholar 

  • Plicher, M.G. and R.L. Rardin. (1988). “Invariant Problem Statistics and Generated Data Validation: Symmetric Traveling Salesman Problems.” ONR-URI Computational Combinatorics Report CC-87-16, Purdue University, West Lafayette, Indiana.

    Google Scholar 

  • Pilcher, M.G. and R.L. Rardin (1992). “Partial Polyhedral Description and Generation of Discrete Optimization Problems with Known Optima.” Naval Research Logistics 39, 839–858.

    Google Scholar 

  • Pinedo, M. (1995). Scheduling: Theory, Algorithms and Systems. New York: Prentice-Hall.

    Google Scholar 

  • Rardin, R.L. and B.W. Lin. (1982). “Test Problems for Computational Experiments-Issues and Techniques.” In M. Beckmann and H. P. Kunzi (eds.), Evaluating Mathematical Programming Techniques,Berlin: Springer-Verlag.

    Google Scholar 

  • Rardin, R.L., C.A. Tovey, and M.G. Pilcher. (1993). “Analysis of a Random Cut Test Instance Generator for the TSP.” In P.M. Pardalos (ed.), Complexity in Numerical Optimization,World Scientific Publishing, pp. 387–405.

  • Sanchis, L.A. (1990). “On the Complexity ofTest Case Generation for NP-Hard Problems.” Information Processing Letters 36, 135–140.

    Google Scholar 

  • Sanchis, L.A. (1994). “Test Case construction for the Vertex Cover Problem.” In Computational Support for Discrete Mathematics. DIMACS Series in Discrete Mathematics and Theoretical American Mathematical Society. Computer Science, Providence, Rhode Island: vol. 15.

    Google Scholar 

  • Sanchis, L.A. (1995). “Generating Hard and Diverse Test Sets for NP-Hard Graph Problems.” Discrete Applied Mathematics 58, 35–66.

    Google Scholar 

  • Song, W.T. and B.W. Schmeiser. (1994). “Reporting the Precision of Simulation Experiments.” In S. Morito, S. Sakasegawa, H. Yoneda, M. Fushimi, and K. Nakano (eds.), New Directions in Simulation for Manufacturing and Communications. pp. 402–407.

  • Tufte, E.R. (1983). The Visual Display of Quantitative Information. Cheshire, Connecticut: Graphics Press.

    Google Scholar 

  • Tufte, E. R. (1990). Envisioning Information. Cheshire, Connecticut: Graphics Press.

    Google Scholar 

  • Tukey, J.W. (1977). Exploratory Data Analysis. Reading, Massachusetts: Addison-Wesley.

    Google Scholar 

  • Uzsoy, R., C.Y. Lee, and L.A. Martin-Vega. (1992). “Scheduling Semiconductor Test Operations: Minimizing Maximum Lateness and Number of Tardy Jobs on a Single Machine.” Naval Research Logistics 39, 369–388.

    Google Scholar 

  • Wolff, R.S. and L. Yaeger. (1993). Visualization of Natural Phenomena. New York: Springer-Verlag.

    Google Scholar 

  • Yoneda, K. (1996). “Optimal Number of Digits to Report.” Journal of the Operations Research Society of Japan 33, 428–434.

    Google Scholar 

  • Zanakis, S.H. (1977). “Computational Experience with Some Nonlinear Optimization Algorithms for Deriving Maximum Likelihood Estimates for Three Parameter Weibull Distribution.” TIMS Studies in Management Science 7, 63–77.

    Google Scholar 

  • Zanakis, S.H. (1979). “A Simulation Study of Some Simple Estimators of the Three-Parameter Weibull Distribution.” Journal of Statistical Computing and Simulation 9, 419–428.

    Google Scholar 

  • Zanakis, S.H., J.R. Evans, and A.A. Vazacopoulos. (1989). “Heuristic Methods and Applications: A Categorized Survey.” European Journal of Operational Research 43, 88–110.

    Google Scholar 

  • Zanakis, S.H. and N. Mann. (1982). “A Good Simple Percentile Estimator of the Weibull Shape Parameter for Use When All Three Parameters Are Unknown.” Naval Research Logistics Quarterly 29, 419–428.

    Google Scholar 

  • Zemel, E. (1981). “Measuring the Quality of Approximate Solutions to Zero-One Programming Problems.” Mathematics of Operations Research 6, 319–332.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Industrial Engineering, Purdue University, West Lafayette, IN, 47907-1287, USA

    Ronald L. Rardin & Reha Uzsoy

Authors
  1. Ronald L. Rardin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Reha Uzsoy
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Rardin, R.L., Uzsoy, R. Experimental Evaluation of Heuristic Optimization Algorithms: A Tutorial. Journal of Heuristics 7, 261–304 (2001). https://doi.org/10.1023/A:1011319115230

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1011319115230

Search

Navigation