Propagating dense systems of integer linear equations

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 Gauss-Seidel propagation, they are substantially faster. We show on standard integer benchmarks how these new propagators can substantially improve propagation performance, in terms of strength of propagation and speed.