Solution Building for Arbitrary System of Linear Inequalities in an Explicit Form

Demetrius V. Shapot, Alexander M. Lukatskii

Energy Research Institute, Russian Academy of Sciences, Moscow, Russia.

DOI: 10.4236/ajcm.2012.21001                

Abstract

The known Fourier-Chernikov algorithm of linear inequality system convolution is complemented with an original procedure of all dependent (redundant) inequalities deletion. The concept of “almost dependent” inequalities is defined and an algorithm for further reducing the system by deletion of these is considered. The concluding algorithm makes it possible to hold actual-time convolution of a general inequality system containing up to 50 variables with the rigorous method of dependent inequalities deletion and up to 100 variables with the approximate method of one. The main application of such an approach consists in solving linear inequality system in an explicit form. These results are illustrated with a series of computer experiments.

Keywords

Linear Inequalities; Convolution; Variable Elimination; Orthogonal Projection Method; Fourier Algorithm; Chernikov Rules; Dependent Inequalities; Redundant Inequalities; Almost Dependent Inequalities; Matrix Cleanup; Coarsening

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	J. B. Fourier, “Solution d’une Question Particulière du Calcul des Inégalités,” Nouvean Bulletin des Sciences par la Société Philomatique de Paris, 1826, p. 99.
[2]	D. V. Shapot, “On the Construction of Orthogonal Projections of Point Sets Defined by a System of Inequalities,” Journal Computational Mathematics and Mathematical Physics, Vol. 11, 1971, pp. 1113-1126.
[3]	S. N. Chernikov, “Linear Inequalities,” Nauka, Мoscow, 1968.
[4]	V. A. Bushenkov and A. V. Lotov, “An Algorithm for Analysis of Inequality Dependences in a Linear System,” Journal Computational Mathematics and Mathematical Physics, Vol. 20, 1980, pp. 562-572.
[5]	A. V. Lotov, “On the Estimate of Stability and the Condition Number of the Solution Set of a System of Linear Inequalities,” Journal Computational Mathematics and Mathematical Physics, Vol. 24, 1984, pp. 1763-1774.
[6]	I. I. Eremin and A. A. Makhnev, “International Workshop on Algebra and Linear optimization dedicated to the 90th Anniversary of the Birth of S. N. Chernikov,” Ural State University Bulletin, Vol. 30, 2004, pp. 183-184.
[7]	D. V. Shapot and A. M. Lukatskii, “A Constructive algorithm for Foldind Large-Scale Systems of Linear Inequalities,” Computational Mathematics and Mathematical Physics, Vol. 48, No. 7, 2008, pp. 1100-1112. doi:10.1134/S0965542508070038
[8]	T. S. Motzkin, H. Raiffa, G. L. Thompson and R. M. Trall, “The Double Description Method,” Contributions to the Theory of Games, Vol. 2, 1953, pp. 51-73.
[9]	F. P. Preparata and M. I. Shamos, “Computational Geometry. An Introduction,” Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1985.
[10]	V. N. Shevchenko and D. V. Gruzdev, “Modifications of Fou-rier-Motskin Algorithm for Triangulation Construction,” Discrete Analysis and Investigation of Operations, Series 2, Vol. 10, 2003, pp. 53-64.
[11]	R. V. Efremov, G. K. Kamenev and A. V. Lotov, “Constructing an Economical Description of a Polytop Using the Duality Theory of Convex Sets,” Doklady Mathematics, Vol. 70, 2004, pp. 934-936.
[12]	A. I. Golikov and Y. G. Evtushenko, “A New Method for Solving Systems of Linear Equalities and Inequalities,” Doklady Mathematics, Vol. 64, 2001, pp. 370-373.
[13]	P. O. Gutman and I. Ioslovich, “On the Generalized Wolf Problem: Preliminary Analysis of Nonnegativity of Large Linear Programs Subject to Group Constrains,” Automation Telemech, No. 8, 2007, pp. 116-125.
[14]	S. Paulraj and P. Sumathi, “A Comparative Study of Redundant Constrains Identification Methods in Lin-ear Programming Problems,” Mathematical Problems in Engineering, Vol. 2010, 2010, pp. 1-16. doi:10.1155/2010/723402
[15]	D. V. Shapot and A. M. Lu-katskii, “A Constructive Algorithm for Building Orthogonal Projections of Polyhedral Sets,” Optimization, Control, Intelligence, Sibirian Energy Institute, Irkutsk, 1995, pp. 77-91.
[16]	D. Hilbert and S. Cohn-Fossen, “Anshauliche Geometrie,” Verlag J. Springer, Berlin, 1932.
[17]	A. D. Alexan-drov, “Convex Polyhedra,” Springer-Verlag, Berlin, 2005.
[18]	V. Klee and G. Minty, “How Good Is the Simplex-Alg- orithm,” Proceedings of the Third Symposium on Inequalities, Los Angeles, 1972, pp. 159-175.
[19]	L. Khachiyan, “A Poly-nomial Algorithm in Linear Programming,” Soviet Mathematics—Doklady, Vol. 20, 1979, pp. 191-194.
[20]	N. Karmarkar, “A New Polinomial Time Algorithm for Linear Programming,” Combinatorics, Vol. 4, No. 4, 1984, pp. 373-395. doi:10.1007/BF02579150
[21]	E. V. Nikolaev, A. P. Burgard and C. D. Maranas “Education and Structural Analysis of Con-cerved Pools for Genom-Scale Metabolic Reconstruction,” Biophysical Journal, Vol. 88, No. 1, 2005, pp. 37-49. doi:10.1529/biophysj.104.043489
[22]	S. S. Keerthi and K. Sridharan, “Solution of Parametrized Linear Inequalities by Fourier Elimination and Its Applications,” Journal of Optimization Theory and Applications, Vol. 65, 1990, pp. 161-169.
[23]	I. N. Karbovsky, A. M. Lukatskii and D. V. Shapot, “Use of Orthogonal Projection Method by the Example of Analysis of Industries Possible Price Response to Natural Monopolies Products Price Shocks,” Proceeding of the Second International Conference MLSD 2008, Institute of Control Sciences, Moscow, 2008, pp. 117-126.