Statistical Analysis of Computational Tests of Algorithms and Heuristics

References

• Ahuja R.K., Mannanti T.L., Orlin J. B.Network Flows (1993) (Prentice Hall, Englewood Cliffs, New Jersey) Google Scholar
• Ahuja R.K., Orlin J.B. Use of Representative Operation Counts in Computational Testing of Algorithms. INFORMS Journal on Computing (1996) 8(3):318–330Link, Google Scholar
• Akritas M.G., Murphy S.A., Lavalle M.P. The Thiel-Sen Estimator with Doubly Censored Data and Applications to Astronomy. Journal of the American Statistical Society (1995) 90(429):170–177Crossref, Google Scholar
• Amini M.M., Barr R.S. Network Reoptimization Algorithms: A Statistically Designed Comparison. INFORMS Journal on Computing (1993) 5(4):395–409Link, Google Scholar
• Amini M.M., Racer M. A Rigorous Computational Comparison of Alternative Solution Methods for the Generalized Assignment Problem. Management Science (1994) 40(7):868–890Link, Google Scholar
• Anderson R.J. The Role of Experiment in the Theory of Algorithms. Fifth DIMACS Challenge Workshop: Experimental Methodology Day (1996) . www.cs.amherst.edu/~dsj/methday.htmlGoogle Scholar
• Balss E., Saltxman M.J. An Algorithm for the Three-Index Assignment Problem. Operations Research (1991) 39(1):150–161Link, Google Scholar
• Barr R.S., Golden B. L., Kelly J.P., Resende M.G.C., Stewart W.R. Designing and Reporting on Computational Experiments with Heuristic Methods. Journal of Heuristics (1995) 1:1–32Crossref, Google Scholar
• Bixby R.E., Boyd E.A., Indovina R.R. MIPLIB: A Test of Real-World Mixed-Integer Programming Problems. SIAM News (1992) 25:16Google Scholar
• Box G.E.P., Cox D.R. An Analysis of Transformations. Journal of the Royal Statistical Society (1964) 26:211–243Google Scholar
• Box G.E.P., Hunter W.G., Hunter J.S.Statistics for Experimenters (1978) (Wiley, New York) 205–207Google Scholar
• Coffin M., Saltzman M.J. (1999) . Robust Regression with Doubly Censored Data, Technical Report 671, Department of Mathematical Sciences, Clemson University, Clemson, SCGoogle Scholar
• Crowder H.P., Dembo R.S., Mulvey J.M. Reporting Computational Results in Mathematical Programming. Mathematical Programming (1978) 15:316–329Crossref, Google Scholar
• Crowder H.P., Dembo R.S., Mulvey J.M. On Reporting Computational Experiments with Mathematical Software. ACM Transactions on Mathematical Software (1979) 5(2):193–203Crossref, Google Scholar
• DATA ANALYSIS PRODUCTS DIVISION, MATHSOFTS-Plus 5 for UNIX Guide to Statistics (1998) (Seattle, WA)Google Scholar
• Dembo R.S., Mulvey J.M., White W.W. On the Analysis and Comparison of Mathematical Programming Algorithms and Software. Computers and Mathematical Programming (1976) (National Bureau of Standards, Washington, DC) 106–116Google Scholar
• Ernst A.T., Krishnamoorthy M. Efficient Algorithms for the Uncapacitated Single Allocation p-hub Median Problem. Location Science (1996) 4:139–154Crossref, Google Scholar
• Ernst A.T., Krishnamoorthy M. An Exact Solution Approach Based on Shortest-Paths for p-hub Median Problems. INFORMS Journal on Computing (1998) 10(2):149–162Link, Google Scholar
• Fourer R., Mehrotra S. Performance of an Augmented System Approach for Solving Least-Squares Problems in an Interior-Point Method for Linear Programming. COAL Newsletter (1991) 19:26–31Google Scholar
• Gay D.M. Electronic Mail Distribution of Linear Programming Test Problems. COAL Newsletter (1985) 13:10–12Google Scholar
• Gilsinn J., Hoffman K., Jackson R.H.F., Leyendecker E., Saunders P., Shier D. Methodology and Analysis for Comparing Discrete Linear L1 Approximation Codes. Communications in Statistics, Simulation, and Computations (1977) B6(4):399–413Crossref, Google Scholar
• Golden B.L., Assad A.A., Wasil E.A., Baker E. Experimentation in Optimization. European Journal of Operational Research (1986) 27:1–16Crossref, Google Scholar
• Golden B.L., Stewart W.R., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B. Empirical Analysis of Heuristics. The Traveling Salesman Problem (1985) (Wiley, New York) 207–249Google Scholar
• Greenberg H.J. Computational Testing: Why, How and How Much. ORSA Journal on Computing (1990) 2(1):94–97Link, Google Scholar
• Gu Z., Nemhauser G.L., Savelsbergh M.W.P. Lifted Cover Inequalities for 0–1 Integer Programs: Computation. INFORMS Journal on Computing (1998) 10(4):427–437Link, Google Scholar
• Hansen P., Jaumard B., Mathon V. Constrained Nonlinear 0–1 Programming. INFORMS Journal on Computing (1993) 5(2):97–119Link, Google Scholar
• Hettmansperger T. P.Statistical Inference Based on Ranks (1984) (Wiley, New York) Google Scholar
• Hicks C.R.Fundamental Concepts in the Design of Experiments (1982) 3rd ed.(Holt, Reinhart & Winston, New York) Google Scholar
• Hoaglin D.C., Klema V.C., Peters S.C. Exploratory Data Analysis in a Study of the Performance of Nonlinear Optimization Routines. ACM Transactions on Mathematical Software (1982) 8(2):145–162Crossref, Google Scholar
• Hoare C.A.R. Quicksort. Computer Journal (1962) 5(1):10–15Crossref, Google Scholar
• Hock W., Schittkowski K.Test Examples for Nonlinear Programming Codes (1981) (Springer-Verlag, New York) . number 187, in Lecture Notes in Economics and Mathematical SystemsCrossref, Google Scholar
• Hoffman A., Mannos M., Solokowsky D., Weighmann N. Computational Experience in Solving Linear Programs. SIAM Journal (1953) 1:1–33Google Scholar
• Hoffman K.L., Jackson R.H.F., Mulvey J.M. In Pursuit of a Methodology for Testing Mathematical Programming Software. Evaluating Mathematical Programming Techniques (1982) (Springer-Verlag, New York) 177–199number 199, in Lecture Notes in Economics and Mathematical SystemsCrossref, Google Scholar
• Hollander M., Wolfe D.A.Nonparametric Statistical Methods (1999) 2nd ed.(Wiley, New York) 56–59Google Scholar
• Hooker J.N. Testing Heuristics: We Have It All Wrong. Journal of Heuristics (1995) 1:33–42Crossref, Google Scholar
• Jackson R.H.F. On the State of the Art of Computational Testing of Mathematical Programming Algorithms. COAL Newsletter (1985) 12:8–13Google Scholar
• Jackson R.H.F., Boggs P.T., Nash S.G., Powell S. Report of the Ad Hoc Committee to Revise the Guidelines for Reporting Computational Experiments in Mathematical Programming. COAL Newsletter (1989) 18:3–14Google Scholar
• Jackson R.H.F., Boggs P.T., Nash S.G., Powell S. Guidelines for Reporting Results of Computational Experiments: Report of the Ad Hoc Committee. Mathematical Programming (1991) 49:413–425Crossref, Google Scholar
• Jackson R.H.F., Mulvey J.M. A Critical Review of Comparisons of Mathematical Programming Algorithms and Software (1953–1977). Journal of Research of the National Bureau of Standards (1978) 83(6):563–584Crossref, Google Scholar
• Johnson D.S. A Theoretician's Guide to the Experimental Analysis of Algorithms. Fifth DIMACS Challenge Workshop: Experimental Methodology Day (1996) . www.cs.amherst.edu/~dsj/methday.htmlGoogle Scholar
• Karmarkar N. Special presentation. TIMS/ORSA National Meeting (1984) (Dallas)Google Scholar
• Layman C.H., O'Neill R.P., White W.W. A Study of the Effect of LP Parameters on Algorithm Performance. Computers and Mathematical Programming (1976) (National Bureau of Standards, Washington, DC) 251–260Google Scholar
• L'ECuyer P. Simulation of Algorithms for Performance Analysis. INFORMS Journal on Computing (1996) 8(1):16–20Link, Google Scholar
• Lottsma F.A., Powell M.J.D. Performance Evaluation of Nonlinear Optimization Methods via Multi-criteria Decision Analysis and via Linear Model Analysis. Nonlinear Optimization 1981 (1982) (Academic, New York) 419–453Google Scholar
• Lustig I.J., Marsten R.E., Shanno D.F. Computational Experience with a Primal-Dual Interior Point Method for Linear Programming. Linear Algebra and its Applications (1991) 152:191–222Crossref, Google Scholar
• McGeoch C. Analyzing Algorithms by Simulation: Variance Reduction Techniques and Simulation Speedups. Computing Surveys (1992) 24(2):195–212Crossref, Google Scholar
• McGeoch C. Challenges in Algorithm Simulation. INFORMS Journal on Computing (1996) 8(1):27–28Link, Google Scholar
• McGeoch C. Toward an Experimental Method for Algorithm Simulation. INFORMS Journal on Computing (1996) 8(1):1–15Link, Google Scholar
• Miele A., Gonzalez S., Mangasarian O.L., Meyer R.R., Robinson S.M. On the Comparative Evaluation of Algorithms for Mathematical Programming Problems. Nonlinear Programming (1978) 3(Academic, New York) 337–359Google Scholar
• Montgomery D.C.Design and Analysis of Experiments (1991) (Wiley, New York) Google Scholar
• Moore D.S., McCabe G.P.Introduction to the Practice of Statistics (1999) (W.H. Freeman, New York) Google Scholar
• Nazareth L., Schlick F., White W.W. The Evaluation of Unconstrained Optimization Routines. Computers and Mathematical Programming (1976) (National Bureau of Standards, Washington, DC) 117–131Google Scholar
• Nelson P.J. Application of the Analysis of Means. Proceedings of the SAS Users Group International Conference (1998) 13:225–230Google Scholar
• Nelson W.Applied Life Data Analysis (1982) (Wiley, New York) Crossref, Google Scholar
• Neter J., Kutner M.H., Nachtshiem C.J., Wasserman J.W.Applied Linear Statistical Models (1998) 4th ed.(Irwin, Homewood, IL) Google Scholar
• Orlin J.B. On Experimental Methods for Algorithm Simulation. INFORMS Journal on Computing (1996) 8(1):21–23Link, Google Scholar
• Ratliff H.D., Pierskalla W. Reporting Computational Experience. Operations Research (1981) 29(2):xi–xivGoogle Scholar
• Rochat Y., Taillard E.D. Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. Journal of Heuristics (1995) 1(1):147–165Crossref, Google Scholar
• Rousseeum P.J., Leroy A.M.Robust Regression and Outlier Detection (1997) (Wiley, New York) Google Scholar
• Saaty T.The Analytic Hierarchy Process (1980) (McGraw-Hill, New York) Google Scholar
• SAS INSTITUTESAS/STAT User's Guide, Version 6 (1989) 4th ed.(SAS Institute, Cary, NC) Google Scholar
• Sedgewick R. The Analysis of Quicksort Programs. Acta Informatica (1977) 7:327–355Crossref, Google Scholar
• Shayan E. A Methodology for Algorithm Comparison in Mathematical Programming. COAL Newsletter (1986) 15:3–11Google Scholar
• Shier D.R. On Algorithm Analysis. INFORMS Journal on Computing (1996) 8(1):24–26Link, Google Scholar
• Tukey J.W.Exploratory Data Analysis (1977) (Addison-Wesley, Reading, MA) Google Scholar
• Vanderbei R.J.Linear Programming: Foundations and Extensions (1996) (Kluwer, Boston, MA) Google Scholar
• White W.W.Computers and Mathematical Programming (1976) (National Bureau of Standards, Washington, DC) Google Scholar
• Zemel E. Measuring the Quality of Approximate Solutions to Zero-One Programming Problems. Mathematics of Operations Research (1981) 6(3):319–332Link, Google Scholar