Patent ID: 6950844

Claim:
A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for solving a system of linear inequalities, the method comprising: receiving a representation of the system of linear inequalities Ax≦b, wherein A is a matrix with m rows corresponding to m inequalities, and with n columns corresponding to n variables, wherein x includes n variable components, and wherein b includes m scalar components; storing the representation in a memory within a computer system; solving the system of linear inequalities Ax≦b by performing a Gaussian elimination process using only positive multipliers so as not to change the sense of any inequaltiy; wherein for a given column j in the matrix A, performing Gaussian elimination process involves, if possible, selecting a primary pivot row r including a primary pivot element, a rj , which is nonzero, selecting a secondary pivot row s including a secondary pivot element, a sj , which is nonzero and opposite in sign to a rj , using the secondary pivot element a sj to zero elements opposite in sign to it in the same column of A, except for the primary pivot element a rj , adding a copy s′ of the secondary pivot row s to the matrix A, thereby increasing the number of rows in the matrix A, and using the primary pivot element a rj to zero elements opposite in sign to it in the same column of A, except for the copy of the secondary pivot element a sj in row s′.