Skip to main content
SpringerLink
Log in

Randomly generated polytopes for testing mathematical programming algorithms

  • Published:
Mathematical Programming Submit manuscript

Abstract

Randomly generated polytopes are used frequently to test and compare algorithms for a variety of mathematical programming problems. These polytopes are constructed by generating linear inequality constraints with coefficients drawn independently from a distribution such as the uniform or the normal.

It is noted that this class of ‘random’ polytopes has a special property: the angles between the hyperplanes, though dependent on the specific distribution used, tend to be equal when the dimension of the space increases.

Obviously this structure of ‘random’ polytopes may bias test results.

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

  1. S. Agmon, “The relaxation method for linear inequalities”,Canadian Journal of Mathematics 6 (1954) 382–392.

    MATH  MathSciNet  Google Scholar 

  2. T.W. Anderson,An introduction to multivariate statistical analysis (Wiley, New York, 1958).

    MATH  Google Scholar 

  3. T.M. Apostol,Mathematical Analysis (Addison-Wesley, London, 1960).

    Google Scholar 

  4. D. Avis and V. Chvatal, “Notes on Bland's pivoting rule”,Mathematical Programming Study 8 (1978) 24–34.

    Google Scholar 

  5. P. Billingsley,Probability and measure (Wiley, New York, 1979).

    MATH  Google Scholar 

  6. T.M. Cover and B. Efron, “Geometrical probability and random points on a hypersphere”,Annals of Mathematical Statistics 38 (1967) 213–220.

    MathSciNet  MATH  Google Scholar 

  7. W.B. van Dam and J. Telgen, “Some computational experiments with a primal-dual surrogate simplex method”, Report 7828 Econometric Institute, Erasmus University (Rotterdam, 1978).

    Google Scholar 

  8. R.S. Dembo and J.M. Mulvey, “On the analyais and comparison of mathematical programming techniques,Proceedings of the bicentennial conference on mathematical programming (Gaithersburg, MD, 1976).

  9. R.S. Garfinkel and P.L. Yu, “A primal-dual surrogate simplex algorithm”, Working Paper 22, College of Business Administration, University of Tennessee (Knoxvill, TN, 1975).

    Google Scholar 

  10. S. Holm and D. Klein, “Size reduction of linear programs with special structure”, Working Paper, Odense University (Odense, Denmark, 1975).

    Google Scholar 

  11. J.P. Ignizio, “On the establishment of standards for comparing algorithm performance”,Interfaces 2 (1971) 8–11.

    Google Scholar 

  12. R.H. Jackson and J.M. Mulvey, “A critical review of methods for comparing mathematical programming algorithms and software 1951–1977”, presented at TIMS XXIII. (Athens, 1977).

  13. M.H. Karwan, J. Telgen and S. Zionts,Redundancy in mathematical programming (Springer-Verlag, New York, Heidelberg, 1982).

    Google Scholar 

  14. L.G. Khachian, “A polynomial algorithm in linear programming”,Soviet Mathematics Doklady 20 (1979) 191–194.

    Google Scholar 

  15. T.M. Liebling, “On the number of iterations of the simplex method”,Operations Research Vefahren 23 (1972) 264–284.

    Google Scholar 

  16. J.H. May and R.L. Smith, “Definition and generation of random polyhedra”, Working Paper 390, Graduate School of Business, University of Pittsburgh (Pittsburgh, PA, 1980).

    Google Scholar 

  17. J.H. May and R.L. Smith, “Random polytopes: their definition, generation and aggregate properties”, Technical Report 80-6, Department of Industrial and Operations Engineering, University of Michigan (Ann Arbor, MI, 1980).

    Google Scholar 

  18. W.M. Michaels and R.P. O'Neill, “User's guide for LPGENR”, Department of Computer Science, Louisiana State University (Baton Rouge, LA, 1975).

    Google Scholar 

  19. T.S. Motzkin and I.J. Schoenberg, “The relaxation method for linear inequalities”,Canadian Journal of Mathematics 6 (1954) 393–404.

    MATH  MathSciNet  Google Scholar 

  20. R.E. Quandt and H.W. Kuhn, “On upper bounds for the number of iterations in solving linear programs”,Operations Research 12 (1964) 161–165.

    MATH  Google Scholar 

  21. B.K. Schmidt and T.H. Mattheis, “The probability that a random polytope is bounded”.Mathematics of Operations Research 2 (1977) 292–296.

    MATH  MathSciNet  Google Scholar 

  22. J. Telgen,Redundancy and linear programs (Mathematical Centre, Amsterdam, 1979).

    Google Scholar 

  23. S. Zionts, “Some empirical tests of the criss-cross method”,Management Science 19 (1972) 406–410.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial Engineering, University of Technology, Eindhoven, The Netherlands

    W. B. van Dam

  2. Econometric Institute, Erasmus University, Rotterdam, The Netherlands

    J. B. G. Frenk

  3. Department of Applied Mathematics, Rabobank Nederland, Zeist, The Netherlands

    J. Telgen

Authors
  1. W. B. van Dam
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. B. G. Frenk
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. J. Telgen
    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

van Dam, W.B., Frenk, J.B.G. & Telgen, J. Randomly generated polytopes for testing mathematical programming algorithms. Mathematical Programming 26, 172–181 (1983). https://doi.org/10.1007/BF02592053

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02592053

Key words

Search

Navigation