- -

A Fine-grained Arc-consistency Algorithm for Non-Normalized Constraint Satisfaction Problems

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

A Fine-grained Arc-consistency Algorithm for Non-Normalized Constraint Satisfaction Problems

Show simple item record

Files in this item

dc.contributor.author Arangú Lobig, Marlene Alicia es_ES
dc.contributor.author Salido Gregorio, Miguel Angel es_ES
dc.date.accessioned 2013-11-04T13:22:33Z
dc.date.issued 2011
dc.identifier.issn 1641-876X
dc.identifier.uri http://hdl.handle.net/10251/33211
dc.description.abstract Constraint programming is a powerful software technology for solving numerous real-life problems. Many of these problems can be modeled as Constraint Satisfaction Problems (CSPs) and solved using constraint programming techniques. However, solving a CSP is NP-complete so filtering techniques to reduce the search space are still necessary. Arc-consistency algorithms are widely used to prune the search space. The concept of arc-consistency is bidirectional, i.e., it must be ensured in both directions of the constraint (direct and inverse constraints). Two of the most well-known and frequently used arc-consistency algorithms for filtering CSPs are AC3 and AC4. These algorithms repeatedly carry out revisions and require support checks for identifying and deleting all unsupported values from the domains. Nevertheless, many revisions are ineffective, i.e., they cannot delete any value and consume a lot of checks and time. In this paper, we present AC4-OP, an optimized version of AC4 that manages the binary and non-normalized constraints in only one direction, storing the inverse founded supports for their later evaluation. Thus, it reduces the propagation phase avoiding unnecessary or ineffective checking. The use of AC4-OP reduces the number of constraint checks by 50% while pruning the same search space as AC4. The evaluation section shows the improvement of AC4-OP over AC4, AC6 and AC7 in random and non-normalized instances. es_ES
dc.description.sponsorship This work has been partially supported by the research projects TIN2010-20976-C02-01 (Ministry of Science and Innovation, Spain) and P19/08 (Ministry of Development, Spain, FEDER). en_EN
dc.language Inglés es_ES
dc.publisher University of Zielona Gora Press es_ES
dc.relation Ministry of Science and Innovation, Spain TIN2010-20976-C02-01 es_ES
dc.relation Ministry of Development, Spain P19/08 es_ES
dc.relation.ispartof International Journal of Applied Mathematics and Computer Science es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Constraint satisfaction problems es_ES
dc.subject Fltering techniques es_ES
dc.subject Consistency algorithms es_ES
dc.subject.classification LENGUAJES Y SISTEMAS INFORMATICOS es_ES
dc.title A Fine-grained Arc-consistency Algorithm for Non-Normalized Constraint Satisfaction Problems es_ES
dc.type Artículo es_ES
dc.embargo.lift 10000-01-01
dc.embargo.terms forever es_ES
dc.identifier.doi 10.2478/v10006-011-0058-2
dc.rights.accessRights Cerrado es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació es_ES
dc.contributor.affiliation Universitat Politècnica de València. Instituto Universitario de Automática e Informática Industrial - Institut Universitari d'Automàtica i Informàtica Industrial es_ES
dc.description.bibliographicCitation Arangu Lobig, MA.; Salido Gregorio, MA. (2011). A Fine-grained Arc-consistency Algorithm for Non-Normalized Constraint Satisfaction Problems. International Journal of Applied Mathematics and Computer Science. 21(4):733-744. doi:10.2478/v10006-011-0058-2 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion Http://dx.doi.org/10.2478/v10006-011-0058-2 es_ES
dc.description.upvformatpinicio 733 es_ES
dc.description.upvformatpfin 744 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 21 es_ES
dc.description.issue 4 es_ES
dc.relation.senia 198823


This item appears in the following Collection(s)

Show simple item record