A unified approach for finding real and integer solutions to systems of linear inequalities

摘要

The variable-elimination method for solving linear inequalities is used for finding integer solutions. Properties of this method enable one to give a simple proof, for a large class of systems of linear inequalities, that if a system in this class has any (real-valued) solution, then it also has an integer solution. This class includes all systems of the form Ax>b where A is any real matrix and b does not contain any negative element. The variable-elimination method has an exponential bound on the storage requirement, and hence on the execution time. These exists a simple strategy aimed at reducing the amount of storage and execution time needed. An experimental implementation was used to explore the effectiveness of this strategy.