Designing and reporting on computational experiments with heuristic methods

• Aarts, E., van Laarhoven, P., Lenstra, J., and Ulder, N. (1994). A computational study of local search algorithms for job shop scheduling.ORSA Journal on Computing, 6(2), 118–125.

  MATH  Google Scholar 

• Ahuja, R., Magnanti, T., and Orlin, J. (1993).Network Flows: Theory, Algorithms, and Applications, Englewood Cliffs, NJ: Prentice Hall.

  Google Scholar 

• Amini, M., and Barr, R. (1990). Network reoptimization algorithms: A statistically designed comparison.ORSA Journal on Computing, 5(4), 395–409.

  Google Scholar 

• Arthur, J., and Frendewey, J. (1988). Generating traveling salemen problems with known optimal tours.Journal of the Operational Research Society, 39(2), 153–159.

  Article  MATH  Google Scholar 

• Arthur, J., and Frendewey, J. (1994). An algorithm for generating minimum cost network flow problems with specific structure and known optimal solutions.Networks, 24(8), 445–454.

  MathSciNet  MATH  Google Scholar 

• Barr, R., and Hickman, B. (1993). Reporting computational experiments with parallel algorithms: Issues, measures, and experts' opinions.ORSA Journal on Computing, 5(1), 2–18.

  MATH  Google Scholar 

• Barr, R., and Hickman, B. (1994). Parallelization strategies for the network simplex algorithm.Operations Research, 42(1), 65–80.

  MATH  Google Scholar 

• Barton, R., and Ivey, Jr., J. (1996). Nelder-mead simplex modifications for simulation optimization. Tech. rep., Department of Industrial and Systems Engineering, Pennsylvania State University, University Park, PA. To appear inManagement Science.

  Google Scholar 

• Battiti, R., and Tecchiolli, G. (1994). Simulated annealing and tabu search in the long run: A comparison on gap tasks.Computers and Mathematics with Applications, 28(6), 1–8.

  Article  MATH  Google Scholar 

• Bland, R., Cheriyan, J., Jensen, D., and Ladányi, L. (1993). An empirical study of min cost flow algorithms. In D. Johnson, and C. McGeoch (Eds.),Network Flows and Matching: First DIMACS Implementation Challenge, Vol. 12 ofDIMACS Series in Discrete Mathematics and Theoretical Computer Science (pp. 119–156): Providence, RI: American Mathematical Society.

  Google Scholar 

• Box, G., and Draper, N. (1969).Evolutionary Operation, A Statistical Method for Process Improvement. New York: John Wiley.

  Google Scholar 

• Bratley, P., Fox, B., and Schrage, L. (1983).A Guide to Simulation. New York: Springer-Verlag

  MATH  Google Scholar 

• Cornuejols, G., Sridharan, R., and Thizy, J. (1991). A comparison of heuristics and relaxations for the capacititated plant location problem.European Journal of Operational Research, 50, 280–297.

  Article  MATH  Google Scholar 

• Crowder, H., Dembo, R., and Mulvey, J. (1980). On reporting computational experiments with mathematical software.ACM Transactions on Mathematical Software, 5, 193–203.

  Article  Google Scholar 

• Dyer, M., and Frieze, A. (1985). A simple heuristic for thep-centre problem.Operations Research Letters, 3(6), 285–288.

  Article  MathSciNet  MATH  Google Scholar 

• Feo, T., and Resende, M. (1995). Greedy randomized adaptive search procedures.Journal of Global Optimization, 6, 109–133.

  Article  MathSciNet  MATH  Google Scholar 

• Fisher, M. (1980). Worst-case analysis of heuristic algorithms.Management Science, 26(1), 1–17.

  MATH  MathSciNet  Google Scholar 

• Floudas, C., and Pardalos, P. (1990).Collection of Test Problems for Constrained Global Optimization Algorithms, Vol. 455 ofLecture Notes in Computer Science. Springer-Verlag.

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

  MATH  Google Scholar 

• Gendreau, M., Hertz, A., and Laporte, G. (1994). A tabu search heuristic for the vehicle routing problem.Management Science, 40(10), 1276–1290.

  MATH  Google Scholar 

• Gilsinn, J., Hoffman, K., Jackson, R., Leyendecker, E., Saunders, P., and Shier, D. (1977). Methodology and analysis for comparing discrete linearl ₁ approximation codes.Communications in Statistics, 136, 399–413.

  Google Scholar 

• Glover, F. (1989). Tabu search-part I.ORSA Journal on Computing, 1(3), 190–206.

  MATH  Google Scholar 

• Glover, F., Karney, D., Klingman, D., and Napier, A. (1974). A computational study on start procedures, basis change criteria, and solution algorithms for transportation problems.Management Science, 20, 793–813.

  MathSciNet  MATH  Google Scholar 

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

  MathSciNet  MATH  Google Scholar 

• Golden, B., and Stewart, W. (1985). Empirical analysis of heuristics. In E. Lawler, J. Lenstra A. Rinnooy Kan, and D. Shmoys (Eds.),The Travelling Salesman Problem, a Guided Tour of Combinatorial Optimization (pp. 207–249). Chichester (U.K.): Wiley.

  Google Scholar 

• Greenberg, H. (1990). Computational testing: Why, how and how much?ORSA Journal on Computing, 2, 7–11.

  Google Scholar 

• Held, M., and Karp, R. (1970). The travelling-salesman problem and minimum spanning trees.Operations Research, 18, 1138–1162.

  MathSciNet  MATH  Google Scholar 

• Held, M., and Karp, R. (1971). The travelling-salesman problem and minimum spanning trees: Part ii.Mathematical Programming, 1, 6–25.

  Article  MathSciNet  MATH  Google Scholar 

• Hochbaum, D., and Shmoys, D. (1985). A best possible heuristic for thek-center problem.Mathematics of Operations Research, 10(2), 180–184.

  MathSciNet  MATH  Google Scholar 

• Holland, J. (1975),Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan Press.

  Google Scholar 

• Hooker, J. (1994). Needed: An empirical science of algorithms.Operations Research, 42(2), 201–212.

  MATH  Google Scholar 

• Hooker, J. (1995). Testing heuristics: We have it all wrong.Journal of Heuristics, 1(1), 33–42.

  MATH  MathSciNet  Google Scholar 

• Hopfield, J., and Tank, D. (1985). Neural computation of decisions in optimization problems.Biological Cybernetics, 52, 141.

  MathSciNet  MATH  Google Scholar 

• Jackson, R., Boggs, P., Nash, S., and Powell, S. (1990). Report of the ad hoc committee to revise the guidelines for reporting computational experiments in mathematical programming.Mathematical Programing, 49, 413–425.

  Article  MathSciNet  Google Scholar 

• Jackson, R., and Mulvey, J. (1978). A critical review of comparisons of mathematical programming algorithms and software (1953–1977).J. Research of the National Bureau of Standards, 83, 563–584.

  MathSciNet  MATH  Google Scholar 

• Johnson, D. (1990). Local optimization and the traveling salesman problem. InProceedings of the 17th Colloquium on Automata, Languages and programming, Lecture Notes in Computer Science 443 (pp. 446–461). Berlin: Springer-Verlag.

  Google Scholar 

• Johnson, D., Bentley, J., McGeoch, L., and Rothberg, E. (1995). Near-optimal solutions to very lage traveling salesman problems. Tech. rep., monograph, in preparation.

• Johnson, D., and Papadimitrious, C. (1985). Performance guarantees for heuristics. In E. Lawler, J. Lenstra, A. Rinnooy Kan, and D. Shmoys (Eds.),The Travelling Salesman Problem, A Guided Tour of Combinatorial Optimization (pp. 145–180). Chichester (U.K.): Wiley.

  Google Scholar 

• Kelly, J., Golden, B., and Assad, A. (1992). Cell suppression: Disclosure protection for sensitive tabular data.Networks, 22(4), 397–417.

  MATH  Google Scholar 

• Kelly, J., Golden, B., and Assad, A. (1993). Large-scale controlled rounding using tabu search and strategic oscillation.Annals of Operations Research, 41, 69–84.

  Article  MATH  Google Scholar 

• Klingman, D., and Mote, J. (1987). Computational analysis of large-scale pure networks. Presented at the Joint National Meeting of ORSA/TIMS, New Orleans.

• Klingman, D., Napier, A., and Stutz, J. (1974). Netgen: A program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems.Management Science, 20, 814–821.

  MathSciNet  MATH  Google Scholar 

• Knox, J. (1994). Tabu search performance on the symmetric travelling salesman problem.Computers & Operations Research, 21(8), 867–876.

  Article  MATH  Google Scholar 

• Lawler, E., Lenstra, J., Kan, A. Rinnooy, and Shmoys, D. (1985).The Travelling Salesman Problem, A Guided Tour of Combinatorial Optimization. Chiehester (U.K.): Wiley.

  Google Scholar 

• Lin, B., and Rardin, R. (1977). Development of a parametric generating procedure for integer programming test problems.Journal of the ACM, 24, 465–472.

  Article  MathSciNet  MATH  Google Scholar 

• Lin, B., and Rardin, R. (1979). Controlled experimental design for statistical comparison of integer programming algorithms.Management Science, 25(12), 33–43.

  Article  MathSciNet  Google Scholar 

• Lin, S., and Kernighan, B. (1973). An effective heuristic algorithm for the traveling-salesman problem.Operations Research, 21(2), 498–516.

  MathSciNet  MATH  Google Scholar 

• Martello, S., and Toth, P. (1990).Knapsack Problems. Chichester (U.K.): Wiley.

  MATH  Google Scholar 

• Mason, R., Gunst, R., and Hess, J. (1989).Statistical Design and Analysis of Experiments. New York: Wiley.

  Google Scholar 

• McGeoch, C. (1986).Experimental Analysis of Algorithms. Ph.D. thesis, Computer Science Department, Carnegie Mellon University, Pittsburgh, PA.

  Google Scholar 

• McGeoch, C. (1995). Toward an experimental method for algorithm simulation.INFORMS Journal on Computing, to appear.

• McGeoch, C. (1992). Analyzing algorithms by simulation: Variance reduction techniques and simulation speedups.ACM Computing Surveys, 24(5), 195–212.

  Article  Google Scholar 

• Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., and Teller, E. (1953). Equation of state calculation by fast computing machines.Journal of Chemical Physics, 21, 1087–1091.

  Article  Google Scholar 

• Montgomery, D. (1984).Design and Analysis of Experiments. New York: Wiley.

  Google Scholar 

• Mulvey, J. (1982).Evaluating Mathematical Programming Techniques. Berlin: Springer-Verlag.

  MATH  Google Scholar 

• Nance, R., Moose, Jr., R., and Foutz, R. (1987). A statistical technique for comparing heuristics: An example from capacity assignment strategies in computer network design.Communications of the ACM, 30(5), 430–442.

  Article  Google Scholar 

• Nelder, J., and Mead, R. (1965). A simplex method for function minimization.Computer Journal, 7, 308–313.

  MATH  Google Scholar 

• Nygard, K., Juell, P., and Kadaba, N. (1990). Neural networks for selecting vehicle routing heuristics.ORSA Journal on Computing, 2(4), 353–364.

  MATH  Google Scholar 

• O'Neill, R. (1982). A comparison of real-world linear programs and their randomly generated analogs. In J. Mulvey (Ed.),Evaluating Mathematical Programming Techniques (pp. 44–59). Berlin: Springer-Verlag.

  Google Scholar 

• Rardin, R., and Lin, B. (1982). Test problems for computational experiments—issues and techniques. In J. Mulvey (Ed.),Evaluating Mathematical Programming Techniques (pp. 8–15). Berlin: Springer-Verlag.

  Google Scholar 

• Reeves, C. (1993a). Evaluation of heuristic performance. In C. Reeves, (Ed.),Modern Heuristic Techniques for Combinatorial Problems. New York: Wiley.

  Google Scholar 

• Reeves, C. (1993b).Evaluation of Heuristic Performance. New York: Wiley.

  Google Scholar 

• Reinelt, G. (1991). TSPLIB—a travelling salesman problem library.ORSA Journal on Computing, 3(4), 376–384.

  MATH  Google Scholar 

• Resende, M., and Ribeiro, C. (1995). A GRASP for graph planarization. Tech. rep., AT&T Bell Laboratories, Murray Hill, NJ.

  Google Scholar 

• Rothfarb, B., Frank, H., Rosebaum, D., Steiglitz, K., and Kleitman, D. (1970). Optimal design of offshore natural gas pipeline systems.Operations Research, 18, 992–1020.

  Google Scholar 

• Stewart, W. (1987). An accelerated branch exchange heuristic for the traveling salesman problem.Networks, 17, 423–437.

  MATH  MathSciNet  Google Scholar 

• Stewart, W., Kelly, J., and Laguna, M. (1995). Solving vehicle routing problems using generalized assignments and tabu search. Tech. rep., Graduate School of Business, College of William and Mary, Williamsburg, VA.

  Google Scholar 

• Taguchi, G., and Wu, Y.-I. (1979).Introduction to Off-Live Quality Control. Central Japan Quality Control Association, Meieki Nakamura-ku Magaya, Japan.

  Google Scholar 

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

  Google Scholar 

• Zanakis, S., Evans, J., and Vazacopoulos, A. (1989). Heuristic methods and applications: A categorized survey.European Journal of Operational Research, 43, 88–110.

  Article  MathSciNet  MATH  Google Scholar 

Download references