A Constructive Algorithm for Folding Large-Scale Systems of Linear Inequalities

作者：Lukatskii A M^*; Shapot D V

来源：Computational Mathematics and Mathematical Physics, 2008, 48(7): 1100-1112.

DOI：10.1134/S0965542508070038

• convex polyhedra
• linear inequalities
• orthogonal projection method
• Fourier-Chernikov algorithm
• coordination of ranges
• redundant inequalities
• complete elimination of redundant inequalities
• simplex method
• elimination of redundant inequalities with coarsening
• numerical experiments

The conventional procedure for folding a system of linear inequalities based on the Fourier-Chernikov algorithm is supplemented with techniques for eliminating redundant inequalities, which considerably counteracts the increase in the system dimension. Exact and approximate methods are proposed, which are brought to algorithmic form and software implementation. Numerical results are discussed.

• 出版日期2008-7