{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T10:44:07Z","timestamp":1709203447689},"reference-count":26,"publisher":"University of Zielona G\u00f3ra, Poland","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,12,1]]},"abstract":"<jats:title>A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems<\/jats:title>\n        <jats:p>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.<\/jats:p>","DOI":"10.2478\/v10006-011-0058-2","type":"journal-article","created":{"date-parts":[[2011,12,21]],"date-time":"2011-12-21T22:11:11Z","timestamp":1324505471000},"page":"733-744","source":"Crossref","is-referenced-by-count":1,"title":["A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems"],"prefix":"10.61822","volume":"21","author":[{"given":"Marlene","family":"Arang\u00fa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miguel","family":"Salido","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"37438","reference":[{"key":"1","first-page":"219","article-title":"AC2001-OP: An arc-consistency algorithm for constraint satisfaction problems","author":"M. Arang\u00fa","year":"2010"},{"key":"2","first-page":"555","article-title":"Constraint programming: In pursuit of the Holy Grail","author":"R. Bart\u00e1k","year":"1999"},{"key":"3","first-page":"7","article-title":"Theory and practice of constraint propagation","author":"R. Bart\u00e1k","year":"2001"},{"key":"4","first-page":"1","article-title":"Constraint propagation and backtracking-based search","author":"R. Bart\u00e1k","year":"2005"},{"key":"5","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/s10845-008-0203-4","article-title":"Constraint satisfaction techniques in planning and scheduling","volume":"21","author":"R. Bart\u00e1k","year":"2010","journal-title":"Journal of Intelligent Manufacturing"},{"key":"6","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0004-3702(94)90041-8","article-title":"Arc-consistency and arc-consistency again","volume":"65","author":"C. Bessiere","year":"1994","journal-title":"Artificial Intelligence"},{"key":"7","unstructured":"Bessiere, C. (2006). Constraint propagation, <i>Technical report<\/i>, CNRS\/University of Montpellier, Montpellier."},{"key":"8","first-page":"108","article-title":"Arc-consistency and arc-consistency again","author":"C. Bessiere","year":"1993"},{"key":"9","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0004-3702(98)00105-2","article-title":"Using constraint metaknowledge to reduce arc consistency computation","volume":"107","author":"C. Bessiere","year":"1999","journal-title":"Artificial Intelligence"},{"key":"10","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/j.artint.2005.02.004","article-title":"An optimal coarse-grained arc-consistency algorithm","volume":"165","author":"C. Bessiere","year":"2005","journal-title":"Artificial Intelligence"},{"issue":"2","key":"11","first-page":"209","article-title":"Fuzzy logic gain scheduling for non-linear servo tracking","volume":"12","author":"M. Brdy\u015b","year":"2002","journal-title":"International Journal of Applied Mathematics and Computer Science"},{"key":"12","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1142\/S0218213098000081","article-title":"Efficient path-consistency propagation","volume":"7","author":"A. Chmeiss","year":"1998","journal-title":"International Journal on Artificial Intelligence Tools"},{"key":"13","volume-title":"Constraint Processing","author":"R. Dechter","year":"2003"},{"issue":"2","key":"14","doi-asserted-by":"publisher","first-page":"219","DOI":"10.2478\/v10006-009-0018-2","article-title":"Input constraints handling in an MPC\/feedback linearization scheme","volume":"19","author":"J. Deng","year":"2009","journal-title":"International Journal of Applied Mathematics and Computer Science"},{"key":"15","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0004-3702(92)90020-X","article-title":"A generic arc-consistency algorithm and its specializations","volume":"57","author":"P. Hentenryck","year":"1992","journal-title":"Artificial Intelligence"},{"issue":"2","key":"16","first-page":"459","article-title":"Self-tuning generalized predictive control with input constraints","volume":"11","author":"A. Kr\u00f3likowski","year":"2001","journal-title":"International Journal of Applied Mathematics and Computer Science"},{"key":"17","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","article-title":"Consistency in networks of relations","volume":"8","author":"A. Mackworth","year":"1977","journal-title":"Artificial Intelligence"},{"key":"18","first-page":"37","article-title":"Reducing checks and revisions in the coarsegrained arc consistency algorithms","volume":"2","author":"D. Mehta","year":"2008","journal-title":"Constraint Programming Letters"},{"issue":"1","key":"19","first-page":"91","article-title":"Evolutionary algorithms for job-shop scheduling","volume":"14","author":"K. Mesghouni","year":"2004","journal-title":"International Journal of Applied Mathematics and Computer Science"},{"key":"20","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0004-3702(86)90083-4","article-title":"Arc and path consistency revised","volume":"28","author":"R. Mohr","year":"1986","journal-title":"Artificial Intelligence"},{"key":"21","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0004-3702(92)90077-B","article-title":"Arc consistency for factorable relations","volume":"53","author":"M. Perlin","year":"1992","journal-title":"Artificial Intelligence"},{"key":"22","volume-title":"Handbook of Constraint Programming","author":"F. Rossi","year":"2008"},{"issue":"2&3","key":"23","first-page":"123","article-title":"Constraint satisfaction\u2014A survey","volume":"11","author":"Z. Ruttkay","year":"1998","journal-title":"CWI Quarterly"},{"issue":"4","key":"24","first-page":"469","article-title":"On the constrained controllability of dynamical systems with multiple delays in the state","volume":"13","author":"B. Sikora","year":"2003","journal-title":"International Journal of Applied Mathematics and Computer Science"},{"key":"25","volume-title":"Foundations of Constraint Satisfaction","author":"E. Tsang","year":"1995"},{"key":"26","first-page":"55","article-title":"The expected value and the variance of the checks required by revision algorithms","volume":"2","author":"M. van Dongen","year":"2008","journal-title":"Constraint Programming Letters"}],"container-title":["International Journal of Applied Mathematics and Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/content.sciendo.com\/view\/journals\/amcs\/21\/4\/article-p733.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/view\/j\/amcs.2011.21.issue-4\/v10006-011-0058-2\/v10006-011-0058-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T10:27:21Z","timestamp":1709202441000},"score":1,"resource":{"primary":{"URL":"https:\/\/content.sciendo.com\/doi\/10.2478\/v10006-011-0058-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12,1]]},"references-count":26,"journal-issue":{"issue":"4"},"URL":"https:\/\/doi.org\/10.2478\/v10006-011-0058-2","relation":{},"ISSN":["1641-876X"],"issn-type":[{"value":"1641-876X","type":"print"}],"subject":[],"published":{"date-parts":[[2011,12,1]]}}}