Representing and solving finite-domain constraint problems using systems of polynomials

Christopher Anthony Jefferson, Peter Jeavons, Martin J. Green, M. R. C. van Dongen

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

In this paper we investigate the use of a system of multivariate polynomials to represent the restrictions imposed by a collection of constraints. One advantage of using polynomials to represent constraints is that it allows many different forms of constraints to be treated in a uniform way. Systems of polynomials have been widely studied, and a number of general techniques have been developed, including algorithms that generate an equivalent system with certain desirable properties, called a Grobner Basis. General algorithms to compute a Grobner Basis have doubly exponential complexity, but we observe that for the systems we use to describe constraint problems over finite domains a Grobner Basis can be computed more efficiently than this. We also describe a family of algorithms, related to the calculation of Grobner Bases, that can be used on any system of polynomials to compute an equivalent system in polynomial time. We show that these modified algorithms can simulate the effect of the local-consistency algorithms used in constraint programming and hence solve certain broad classes of constraint problems in polynomial time. Finally we discuss the use of adaptive consistency techniques for systems of polynomials.

Original languageEnglish
Pages (from-to)359-382
Number of pages24
JournalAnnals of Mathematics and Artificial Intelligence
Volume67
Issue number3-4
DOIs
Publication statusPublished - Mar 2013

Keywords

  • Constraint satisfaction
  • Groebner basis
  • Consistency
  • BUCHBERGER ALGORITHM
  • GROBNER BASES
  • CONSISTENCY

Fingerprint

Dive into the research topics of 'Representing and solving finite-domain constraint problems using systems of polynomials'. Together they form a unique fingerprint.

Cite this