Propagating dense systems of integer linear equations

Abstract

In interval propagation approaches to solving non-linear constraints over reals it is common to build stronger propagators from systems of linear equations. This, as far as we are aware, is not pursued for integer finite domain propagation. In this paper we show how we can add preconditioning Gauss-Seidel based propagators to an integer propagation solver. The Gauss-Seidel based propagators make use of interval arithmetic which is substantially slower than integer arithmetic. We show how we can build new integer propagators from the result of preconditioning that no longer require interval arithmetic to be performed. Although the resulting propagators may be slightly weaker than the original..