Abstract
The problem of eliminating unknowns from a system of linear inequalities is considered. A new fast technique for verifying Chernikov rules in Fourier-Motzkin elimination is proposed, which is an adaptation of the “graph” test for adjacency in the double description method. Numerical results are presented that confirm the effectiveness of this technique.
Similar content being viewed by others
References
S. N. Chernikov, Linear Inequalities (Nauka, Moscow, 1968) [in Russian].
G. Ziegler, Lectures on Polytopes (Springer New York, 1998).
S. N. Chernikov, “Convolution of systems of linear inequalities,” Dokl. Akad. Nauk SSSR 131(3), 518–521 (1960).
S. N. Chernikov, “The convolution of finite systems of linear inequalities,” USSR Comput. Math. Math. Phys. 5(1), 1–24 (1965).
T. S. Motzkin, H. Raiffa, G. L. Thompson, and R. M. Thrall, “The double description method,” in Contributions to the Theory of Games, Annals of Mathematics Studies (Princeton Univ. Press, Princeton, New Jersey, 1953), Vol. 28, No. 2, pp. 51–73.
K. Fukuda and A. Prodon, “Double description method revisited,” Combinatorics and Computer Science (Springer-Verlag, New York, 1996), pp. 91–111.
N. Yu. Zolotykh, “New modification of the double description method for constructing the skeleton of a polyhedral cone,” Comput. Math. Math. Phys. 51(1), 146–156 (2012).
A. M. Lukatskii and D. V. Shapot, “A constructive algorithm for folding large-scale systems of linear inequalities,” Comput. Math. Math. Phys. 48(7), 1100–1112 (2008).
M. M. Deza and M. Laurent, Geometry of Cuts and Metrics (Springer-Verlag, Berlin, 1997; MTsNMO, Moscow, 2001).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © S.I. Bastrakov, N.Yu. Zolotykh, 2015, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2015, Vol. 55, No. 1, pp. 165–172.
Rights and permissions
About this article
Cite this article
Bastrakov, S.I., Zolotykh, N.Y. Fast method for verifying Chernikov rules in Fourier-Motzkin elimination. Comput. Math. and Math. Phys. 55, 160–167 (2015). https://doi.org/10.1134/S0965542515010042
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0965542515010042