Hit-and-run algorithms for the indentification of nonredundant linear inequalities

H.C.P. Berbee, C.G.E. Boender, A.H.G. Rinnooy Kan, C.L. Scheffer, R.L. Smith, Jan Telgen

Research output: Contribution to journalArticleProfessional

52 Citations (Scopus)
70 Downloads (Pure)

Abstract

Two probabilistic hit-and-run algorithms are presented to detect nonredundant constraints in a full dimensional system of linear inequalities. The algorithms proceed by generating a random sequence of interior points whose limiting distribution is uniform, and by searching for a nonredundant constraint in the direction of a random vector from each point in the sequence. In the hypersphere directions algorithm tile direction vector is drawn from a uniform distribution on a hypersphere. In tile computalionalb superior coordinate directions algorithm a search is carried out along one of the coordinate vectors. The algorithms are terminated through the use of a Bayesian stopping rule. Computational experience with the algorithms and the stopping rule will be reported.
Original languageEnglish
Pages (from-to)184-207
Number of pages24
JournalMathematical programming
Volume37
Issue number2
DOIs
Publication statusPublished - 1987

Keywords

  • System of linear inequalities
  • Redundancy
  • Probabilistic hit-and-run algorithms
  • Uniform interior points
  • Bayesian stopping rule

Fingerprint Dive into the research topics of 'Hit-and-run algorithms for the indentification of nonredundant linear inequalities'. Together they form a unique fingerprint.

  • Cite this

    Berbee, H. C. P., Boender, C. G. E., Rinnooy Kan, A. H. G., Scheffer, C. L., Smith, R. L., & Telgen, J. (1987). Hit-and-run algorithms for the indentification of nonredundant linear inequalities. Mathematical programming, 37(2), 184-207. https://doi.org/10.1007/BF02591694