Séance Séminaire

Séminaire ACSIOM

Integer ABS class of algorithms for solving linear Diophantine equations

In the past two decades, a class of methods for solving linear systems of equations, first introduced by Abaffy, Broyden, and Spedicato (ABS) in 1984, has been extended to solve nonlinear systems of equations and optimization problems. These methods are a generalization of the rank-one reducing process proposed by Egervary in 1955, and can also be explained by a rank-one reducing formula given by Wedderburn in 1934. In 2001, we presented an ABS-type class of algorithms for solving linear Diophantine systems of equations giving complete characterizations of the integer solutions. Later in 2003, we extended the algorithms to solve the scaled (or preconditioned) Diophantine systems. Recently, we have shown how to efficiently solve a rank one modified Diophantine system using the information obtained from solving the original system by an integer ABS algorithm. The updating strategy can be quite useful in implementing integer programming algorithms based on active set strategies. We describe the integer ABS approach as cited here.