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

63 Citations (Scopus)
178 Downloads (Pure)


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
Issue number2
Publication statusPublished - 1987


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


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