Method and apparatus for solving systems of linear inequalities

Abstract

One embodiment of the present invention provides a system that performs a procedure to solve a system of linear inequalities. During operation, the system receives a representation of the system of linear inequalities Ax≦b, wherein Ax≦b can be a linearized form of a system of nonlinear equations. Within this representation, A is an interval matrix with m rows corresponding to m inequalities, and with n columns corresponding to n variables, the vector x includes n variable components, and the vector b includes m scalar interval components. The system solves 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 inequality. For a given column j in A, performing the Gaussian elimination process involves attempting to select a primary pivot row r including a primary pivot element, a, which does not contain zero, and attempting to select a secondary pivot row s including a secondary pivot element, a, which does not contain zero and is opposite in sign to a. If r and s are successfully selected, the system uses the secondary pivot element ato zero elements opposite in sign to it in the same column of A, except for the primary pivot element a. The system also adds a copy s' of the secondary pivot row s to the matrix A, thereby increasing the number of rows in the matrix A. Next, the system uses the primary pivot element are to zero elements opposite in sign to it in the same column of A, except for the copy of the secondary pivot element ain row s′.