Software method for solving systems of linear equations having integer variables

摘要

This invention describes a software method for computers for solving integer programming problems containing systems of linear equations where part of or all of the variables may take only integer values. Said software method consists of 3 main steps. First, all of or part of said system is regularized such that the variable-coefficients of the regularized part of said system satisfy some well defined properties. In a second step, parameterized solutions are computed for each equation of said system. In a third step, solutions to said system are determined by finding solutions which are common to all equations of said system. Furthermore, the solutions of an equation of said system may be determined by sorting two or more of the variable-coefficients of a said equation according to ascending or descending magnitude. Finally, prior to executing said 3 steps, said system may be conditioned such any variable-coefficient of the system is non-zero.