A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems

Marlene Arangú; Miguel A. Salido

International Journal of Applied Mathematics and Computer Science (2011)

  • Volume: 21, Issue: 4, page 733-744
  • ISSN: 1641-876X

Abstract

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

How to cite

top

Marlene Arangú, and Miguel A. Salido. "A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems." International Journal of Applied Mathematics and Computer Science 21.4 (2011): 733-744. <http://eudml.org/doc/208084>.

@article{MarleneArangú2011,
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. Arcconsistency 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.},
author = {Marlene Arangú, Miguel A. Salido},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {constraint satisfaction problems; filtering techniques; consistency algorithms},
language = {eng},
number = {4},
pages = {733-744},
title = {A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems},
url = {http://eudml.org/doc/208084},
volume = {21},
year = {2011},
}

TY - JOUR
AU - Marlene Arangú
AU - Miguel A. Salido
TI - A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems
JO - International Journal of Applied Mathematics and Computer Science
PY - 2011
VL - 21
IS - 4
SP - 733
EP - 744
AB - 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. Arcconsistency 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.
LA - eng
KW - constraint satisfaction problems; filtering techniques; consistency algorithms
UR - http://eudml.org/doc/208084
ER -

References

top
  1. Arangú, M., Salido, M. A. and Barber, F. (2010). AC2001OP: An arc-consistency algorithm for constraint satisfaction problems, 23rd International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2010, Córdoba, Spain, pp. 219-228. 
  2. Barták, R. (1999). Constraint programming: In pursuit of the Holy Grail, Proceedings of the Week of Doctoral Students (WDS99), Prague, Czech Republic, Part IV, pp. 555-561. 
  3. Barták, R. (2001). Theory and practice of constraint propagation, Proceedings of the 3rd Workshop on Constraint Programming in Decision and Control, Gliwice, Poland, pp. 7-14. 
  4. Barták, R. (2005). Constraint propagation and backtrackingbased search, First International Summer School on Constraint Programming, Acquafredda di Maratea, Italy, pp. 1-43. 
  5. Barták, R., Salido, M.A. and Rossi, F. (2010). Constraint satisfaction techniques in planning and scheduling, Journal of Intelligent Manufacturing 21: 5-15. 
  6. Bessiere, C. (1994). Arc-consistency and arc-consistency again, Artificial Intelligence 65: 179-190. 
  7. Bessiere, C. (2006). Constraint propagation, Technical report, CNRS/University of Montpellier, Montpellier. 
  8. Bessiere, C. and Cordier, M. (1993). Arc-consistency and arcconsistency again, Proceedings of the 11th National Conference on Artificial Intelligence (AAAI-93), Washington, DC, USA, pp. 108-113. 
  9. Bessiere, C., Freuder, E. and Régin, J.C. (1999). Using constraint metaknowledge to reduce arc consistency computation, Artificial Intelligence 107: 125-148. Zbl0911.68192
  10. Bessiere, C., Régin, J.C., Yap, R. and Zhang, Y. (2005). An optimal coarse-grained arc-consistency algorithm, Artificial Intelligence 165: 165-185. Zbl1132.68691
  11. Brdyś, M.A. and Littler, J.J. (2002). Fuzzy logic gain scheduling for non-linear servo tracking, International Journal of Applied Mathematics and Computer Science 12(2): 209-219. Zbl1004.93502
  12. Chmeiss, A. and Jegou, P. (1998). Efficient path-consistency propagation, International Journal on Artificial Intelligence Tools 7: 121-142. 
  13. Dechter, R. (2003). Constraint Processing, Morgan Kaufmann, San Francisco, CA. Zbl1057.68114
  14. Deng, J., Becerra, V.M. and Stobart, R. (2009). Input constraints handling in an MPC/feedback linearization scheme, International Journal of Applied Mathematics and Computer Science 19(2): 219-232, DOI: 10.2478/v10006-009-00182. Zbl1167.93336
  15. Hentenryck, P.V., Deville, Y. and Teng, C.M. (1992). A generic arc-consistency algorithm and its specializations, Artificial Intelligence 57: 291-321. Zbl0763.68059
  16. Królikowski, A. and Jerzy, D. (2001). Self-tuning generalized predictive control with input constraints, International Journal of Applied Mathematics and Computer Science 11(2): 459-479. Zbl0969.93500
  17. Mackworth, A.K. (1977). Consistency in networks of relations, Artificial Intelligence 8: 99-118. Zbl0341.68061
  18. Mehta, D. (2008). Reducing checks and revisions in the coarsegrained arc consistency algorithms, Constraint Programming Letters 2: 37-53. 
  19. Mesghouni, K., Hammadi, S. and Borne, P. (2004). Evolutionary algorithms for job-shop scheduling, International Journal of Applied Mathematics and Computer Science 14(1): 91-103. Zbl1171.90402
  20. Mohr, R. and Henderson, T. (1986). Arc and path consistency revised, Artificial Intelligence 28: 225-233. 
  21. Perlin, M. (1992). Arc consistency for factorable relations, Artificial Intelligence 53: 329-342. Zbl1193.68140
  22. Rossi, F., Van Beek, P. and Walsh, T. (2008). Handbook of Constraint Programming, Elsevier Science and Technology, Amsterdam. Zbl1175.90011
  23. Ruttkay, Z. (1998). Constraint satisfaction-A survey, CWI Quarterly 11(2&3): 123-162. Zbl0911.68073
  24. Sikora, B. (2003). On the constrained controllability of dynamical systems with multiple delays in the state, International Journal of Applied Mathematics and Computer Science 13(4): 469-479. Zbl1042.93010
  25. Tsang, E. (1995). Foundations of Constraint Satisfaction, Academic Press, London/San Diego, CA . 
  26. van Dongen, M., Dieker, A. and Sapozhnikov, A. (2008). The expected value and the variance of the checks required by revision algorithms, Constraint Programming Letters 2: 55-77. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.