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.
- System of linear inequalities
- Probabilistic hit-and-run algorithms
- Uniform interior points
- Bayesian stopping rule
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