Propagating dense systems of integer linear equations

Thibaut Feydy, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

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 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.

Original languageEnglish
Title of host publicationProceedings of the 2007 ACM Symposium on Applied Computing
Pages306-310
Number of pages5
DOIs
Publication statusPublished - 18 Oct 2007
Externally publishedYes
EventACM Symposium on Applied Computing 2007 - Seoul, Korea, Republic of (South)
Duration: 11 Mar 200715 Mar 2007
Conference number: 22nd
https://dl.acm.org/doi/proceedings/10.1145/1244002 (Proceedings)

Publication series

NameProceedings of the ACM Symposium on Applied Computing

Conference

ConferenceACM Symposium on Applied Computing 2007
Abbreviated titleSAC 2007
CountryKorea, Republic of (South)
CitySeoul
Period11/03/0715/03/07
Internet address

Keywords

  • Constraint programming
  • Constraint propagation
  • Gaussian elimination
  • Linear equations

Cite this