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

Arangú, M. ; Salido, M. A.

International Journal of Applied Mathematics and Computer Science, Tome 21 (2011) no. 4, pp. 733-744.

Résumé

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

Détail

Keywords: constraint satisfaction problems, filtering techniques
Mots-clés : problemy z ograniczeniami, technika filtrowania, algorytm zgodności

Bibliographie

[1] Arangú, M., Salido, M. A. and Barber, F. (2010). AC2001-OP: 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´ordoba, 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 backtracking-based 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 arc-consistency 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.

[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.

[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.

[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.

[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-0018-2.

[15] Hentenryck, P. V., Deville, Y. and Teng, C. M. (1992). A generic arc-consistency algorithm and its specializations, Artificial Intelligence 57: 291-321.

[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.

[17] Mackworth, A. K. (1977). Consistency in networks of relations, Artificial Intelligence 8: 99-118.

[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.

[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.

[22] Rossi, F., Van Beek, P. and Walsh, T. (2008). Handbook of Constraint Programming, Elsevier Science and Technology, Amsterdam.

[23] Ruttkay, Z. (1998). Constraint satisfaction-A survey, CWI Quarterly 11(23): 123-162.

[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.

[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.