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, Tome 21 (2011), p. 733-744 / Harvested from The Polish Digital Mathematics Library

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

Détail

Publié le : 2011-01-01

Zbl 1288.90090

EUDML-ID : urn:eudml:doc:208084

Bibliographie

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

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

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

[003] Barták, R. (2005). Constraint propagation and backtrackingbased search, First International Summer School on Constraint Programming, Acquafredda di Maratea, Italy, pp. 1-43.

[004] Barták, R., Salido, M.A. and Rossi, F. (2010). Constraint satisfaction techniques in planning and scheduling, Journal of Intelligent Manufacturing 21: 5-15.

[005] Bessiere, C. (1994). Arc-consistency and arc-consistency again, Artificial Intelligence 65: 179-190.

[006] Bessiere, C. (2006). Constraint propagation, Technical report, CNRS/University of Montpellier, Montpellier.

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

[008] Bessiere, C., Freuder, E. and Régin, J.C. (1999). Using constraint metaknowledge to reduce arc consistency computation, Artificial Intelligence 107: 125-148. | Zbl 0911.68192

[009] Bessiere, C., Régin, J.C., Yap, R. and Zhang, Y. (2005). An optimal coarse-grained arc-consistency algorithm, Artificial Intelligence 165: 165-185. | Zbl 1132.68691

[010] 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. | Zbl 1004.93502

[011] Chmeiss, A. and Jegou, P. (1998). Efficient path-consistency propagation, International Journal on Artificial Intelligence Tools 7: 121-142.

[012] Dechter, R. (2003). Constraint Processing, Morgan Kaufmann, San Francisco, CA. | Zbl 1057.68114

[013] 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. | Zbl 1167.93336

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

[015] 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. | Zbl 0969.93500

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

[017] Mehta, D. (2008). Reducing checks and revisions in the coarsegrained arc consistency algorithms, Constraint Programming Letters 2: 37-53.

[018] 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. | Zbl 1171.90402

[019] Mohr, R. and Henderson, T. (1986). Arc and path consistency revised, Artificial Intelligence 28: 225-233.

[020] Perlin, M. (1992). Arc consistency for factorable relations, Artificial Intelligence 53: 329-342. | Zbl 1193.68140

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

[022] Ruttkay, Z. (1998). Constraint satisfaction-A survey, CWI Quarterly 11(2&3): 123-162. | Zbl 0911.68073

[023] 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. | Zbl 1042.93010

[024] Tsang, E. (1995). Foundations of Constraint Satisfaction, Academic Press, London/San Diego, CA .

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