Representing and Solving Finite−Domain Constraint Problems Using Systems of Polynomials
In this paper we investigate the use of a system of multivariate polynomials to represent the restrictions imposed by a collection of constraints. The advantage of using polynomials to represent constraints is that it allows many different forms of constraints to be treated in a uniform way. Systems...
| Main Authors: | , , , |
|---|---|
| Formato: | Report |
| Publicado: |
Oxford University Computing Laboratory
2007
|
| _version_ | 1826306681163743232 |
|---|---|
| author | Jefferson, C Jeavons, P Green, M van Dongen, M |
| author_facet | Jefferson, C Jeavons, P Green, M van Dongen, M |
| author_sort | Jefferson, C |
| collection | OXFORD |
| description | In this paper we investigate the use of a system of multivariate polynomials to represent the restrictions imposed by a collection of constraints. The 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 Gröbner Basis. General algorithms to compute a Gröbner Basis have doubly exponential complexity, but we observe that for the systems we use to describe constraint problems over finite domains a Gröbner Basis can be computed more efficiently than this. We also describe a family of algorithms, related to the calculation of Gröbner 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. Finally, we describe how these algorithms can be used in a similar way to local consistency techniques to solve certain broad classes of constraint problems in polynomial time. |
| first_indexed | 2024-03-07T06:51:39Z |
| format | Report |
| id | oxford-uuid:fcc2b14a-daf2-486d-a81b-c3a71f2d4e63 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T06:51:39Z |
| publishDate | 2007 |
| publisher | Oxford University Computing Laboratory |
| record_format | dspace |
| spelling | oxford-uuid:fcc2b14a-daf2-486d-a81b-c3a71f2d4e632022-03-27T13:23:22ZRepresenting and Solving Finite−Domain Constraint Problems Using Systems of PolynomialsReporthttp://purl.org/coar/resource_type/c_93fcuuid:fcc2b14a-daf2-486d-a81b-c3a71f2d4e63Department of Computer ScienceOxford University Computing Laboratory2007Jefferson, CJeavons, PGreen, Mvan Dongen, MIn this paper we investigate the use of a system of multivariate polynomials to represent the restrictions imposed by a collection of constraints. The 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 Gröbner Basis. General algorithms to compute a Gröbner Basis have doubly exponential complexity, but we observe that for the systems we use to describe constraint problems over finite domains a Gröbner Basis can be computed more efficiently than this. We also describe a family of algorithms, related to the calculation of Gröbner 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. Finally, we describe how these algorithms can be used in a similar way to local consistency techniques to solve certain broad classes of constraint problems in polynomial time. |
| spellingShingle | Jefferson, C Jeavons, P Green, M van Dongen, M Representing and Solving Finite−Domain Constraint Problems Using Systems of Polynomials |
| title | Representing and Solving Finite−Domain Constraint Problems Using Systems of Polynomials |
| title_full | Representing and Solving Finite−Domain Constraint Problems Using Systems of Polynomials |
| title_fullStr | Representing and Solving Finite−Domain Constraint Problems Using Systems of Polynomials |
| title_full_unstemmed | Representing and Solving Finite−Domain Constraint Problems Using Systems of Polynomials |
| title_short | Representing and Solving Finite−Domain Constraint Problems Using Systems of Polynomials |
| title_sort | representing and solving finite domain constraint problems using systems of polynomials |
| work_keys_str_mv | AT jeffersonc representingandsolvingfinitedomainconstraintproblemsusingsystemsofpolynomials AT jeavonsp representingandsolvingfinitedomainconstraintproblemsusingsystemsofpolynomials AT greenm representingandsolvingfinitedomainconstraintproblemsusingsystemsofpolynomials AT vandongenm representingandsolvingfinitedomainconstraintproblemsusingsystemsofpolynomials |