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 the direction vector is drawn from a uniform distribution on a hypersphere. In the computationally 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.B. Ash,Real Analysis and Probability, (Academic Press, New York, 1972).
M.L. Balinski, “An algorithm for finding all vertices of convex polyhedral sets”,Journal of the Society of Industrial Applied Mathematics 9 (1961) 72–88.
C.G.E. Boender, and A.H.G. Rinnooy Kan, “A Bayesian analysis of the number of cells of a multinomial distribution”The Statistician 32 (1983a) 240–248.
C.G.E. Boender and A.H.G. Rinnooy Kan, “Bayesian estimation of animal population size”, Report 8322/0 Econometric Institute, Erasmus University Rotterdam (Rotterdam, 1983b).
C.G.E. Boender, “The generalized multinomial distribution: A Bayesian analysis and applications”, Ph.D. Thesis, Erasmus University Rotterdam (Rotterdam, 1984).
A. Boneh and A. Golan, “Constraints redundancy and feasible region boundedness by random feasible points generated”, paper presented at EURO III (1979).
A. Boneh, “A probabilistic algorithm identifying redundancy by a random feasible point generator (RFPG)”, in: Karwan et al. (1983).
G.H. Bradley, G.G. Brown and G.W. Graves, “Structural redundancy in large scale optimization models”, Technical Report CA 93940, Naval Postgraduate School (Monterey, 1980); also in: Karwan et al. (1983).
A.L. Brearly, G. Mitra and H.P. Williams, “Analysis of mathematical programming problems prior to applying the simplex algorithm”,Mathematical Programming 8 (1975) 54–83.
T. Gal, “Zur Identifikation redundanter Nebenbedingungen in linearen Programmen”,Zeitschrift für Operations Research 19 (1975) 19–28.
T. Gal, “Zur Identifikation redundanter Nebenbedingungen in linearen Programmen”,Zeitschrift für Operations Research 19 (1975) 19–28.
I.J. Good,The Estimation of Probabilities, Research Monograph, no. 30, (The M.I.T. Press, Cambridge, MA, 1965).
M.H. Karwan, V. Lotfi, J. Telgen and S. Zionts, eds.,Redundancy in Mathematical Programming (Springer-Verlag, Berlin, 1983).
D.V. Lindley,Bayesian Statistics, A Review (Society for Industrial and Applied Mathematics, Philadelphia, PA, 1978).
J. Lisy, “Metody pro nalezini redundant omezini v ulohach linearniho programovani”,Economicko Mathematicky Obzor 7 (1971) 285–198.
T.H. Mattheis, “An algorithm for determining irrelevant constraints and all vertices in systems of linear inequalities”,Operations Research 21 (1973) 247–260.
G.L. Meyerman, “Betekenis van een aantal cultuurtechnische faktoren voor de ontwikkelings-mogelijkheden van veenkoloniale akkerbouwbedrijven”, Dissertation, Agricultural University Wageningen, The Netherlands (Wageningen), (1966).
S. Orey,Limit Theorems for Markov Chain Transition Probabilities (Van Nostrand, New York, 1971).
M.O. Rabin, “Probabilistic algorithms”, in: J.F. Traub, ed.,Algorithms and Complexity (Academic Press London, 1976).
R.L. Smith “Monte Carlo procedures for generating random feasible solutions to mathematical programs”, ORSA/TIMS Conference Washington, DC (1980).
R.L. Smith, “Efficient Monte Carlo procedures for generating points uniformly over bounded regions”,Operations Research 32 (1984) 1296–1308.
J. Telgen,Redundancy and Linear Programs (Mathematical Centre, Amsterdam, 1979).
J. Telgen, Private Communication with A. Boneh (1980).
G.L. Thompson, F.M. Tonge and S. Zionts, “Techniques for removing non-binding constraints and extraneous variables from linear programming problems”,Management Science 12 (1966) 588–608.
G.T. Timmer, “Global optimization: A stochastic approach”, Ph.D. Thesis, Erasmus University Rotterdam (Rotterdam, 1984).
H.J. Tischer, “Mathematische Verfahren zur Reduzierung der Zeilen und Spaltenzahl linearer Optimierungsaufgaben”, Dissertation, Zentral-Institut für Fertigungstechnik des Maschinenbaues, Karl Marx Stadt, DDR (1968).
S.S. Wilks,Mathematical Statistics (Wiley, New York, 1962).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Berbee, H.C.P., Boender, C.G.E., Rinnooy Ran, A.H.G. et al. Hit-and-run algorithms for the identification of nonredundant linear inequalities. Mathematical Programming 37, 184–207 (1987). https://doi.org/10.1007/BF02591694
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02591694