Propagating systems of dense linear integer constraints

Abstract

In interval propagation approaches to solving nonlinear 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 use interval Gauss-Jordan elimination to build stronger propagators for an integer propagation solver. In a similar fashion we present an interval Fourier elimination preconditioning technique to generate redundant linear constraints from a system of linear inequalities. We show how to convert the resulting interval propagators into integer propagators. This allows us to use existing integer solvers. We give experiments that sh..