Abstract
A new approach is given for the analysis of random methods for detecting necessary constraints in systems of linear inequality constraints. This new approach directly accounts for the fact that two constraints are detected as necessary (hit) at each iteration of a random method. The significance of this two-hit analysis is demonstrated by comparing it with the usual one-hit analysis.
Similar content being viewed by others
References
M. Abramowitz and I.A. Stegun, eds.,Handbook of Mathematical Functions (National Bureau of Standards, Washington, DC, 1964).
H.C.P. Berbee, C.G.E. Boender, A.H.G. Rinooy Kan, C.L. Sheffer, R.L. Smith and T. Telgen, “Hit-and-run algorithms for the identification of nonredundant linear inequalities,”Mathematical Programming 37 (1987) 184–207.
A. Boneh, “Preduce—A probabilistic algorithm identifying redundancy by a random feasible point generator (RFPG),” in: M.H. Karwan, V. Lotfi, J. Telgen and S. Zionts, eds.,Redundancy in Mathematical Programming (Springer-Verlag, Berlin, 1983) pp. 108–134.
A. Boneh and A. Golan, “Constraints' redundancy and feasible region boundedness by random feasible point generator (RFPG), “contributed paper, Third European congress on operations research, EURO III (Amsterdam, The Netherlands, April 1979).
R.J. Caron, J.F. McDonald, R.L. Smith and J. Telgen, “Random methods for detecting necessary linear inequality constraints: Stopping Rules,” Windsor Mathematics Report WMR 86-03, Department of Mathematics and Statistics, University of Windsor (Windsor, Ontario, 1986).
W. Feller,An Introduction to Probability Theory and its Applications, Volume 1, Third Edition (John Wiley and Sons, New York, NY, 1968).
M.H. Karwan, V. Lotfi, J. Telgen and S. Zionts, eds.,Redundancy in Mathematical Programming (Springer-Verlag, Berlin, 1983).
R.L. Smith, “Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions,”Operations Research 32 (1984) 1296–1308.
R.L. Smith and J. Telgen, “Random methods for identifying nonredundant constraints,” Technical Report No. 81-4, Department of Industrial and Operations Engineering, The University of Michigan (Ann Arbor, MI, 1981).
J. Telgen, private communication with A. Boneh (1980).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Caron, R.J., McDonald, J.F. A new approach to the analysis of random methods for detecting necessary linear inequality constraints. Mathematical Programming 43, 97–102 (1989). https://doi.org/10.1007/BF01582281
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582281