Propagating systems of dense linear integer constraints

Thibaut Feydy, Peter J. Stuckey

Research output: Contribution to journalArticleResearchpeer-review


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 show how these preconditioning techniques can improve propagation performance on dense systems.

Original languageEnglish
Pages (from-to)235-253
Number of pages19
Issue number2
Publication statusPublished - 1 Jun 2009
Externally publishedYes


  • Constraint propagation
  • Fourier elimination
  • Gauss-Jordan elimination
  • Interval arithmetic
  • Linear constraints

Cite this