×

Solving weighted CSP by maintaining arc consistency. (English) Zbl 1086.68592

Summary: Recently, a general definition of Arc Consistency (AC) for soft constraint frameworks has been proposed by T. Schiex [Lect. Notes Comput. Sci. 1894, 411–424 (2000; Zbl 1044.68797)]. We specialize this definition to weighted CSP and introduce two \(O(ed^3)\) enforcing algorithms. Then, we refine the definition and introduce a stronger form of arc consistency (\(\text{AC}^*\)) along with two \(O(n^{2}d^{2}+ed^{3})\) algorithms. As in the CSP case, an important application of AC isto combine it with search. We empirically demonstrate that a branch and bound algorithm that maintains either AC or \(\text{AC}^*\) is a state-of-the-art general solver for weighted CSP. Our experiments cover binary Max-CSP and Max-SAT problems.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Citations:

Zbl 1044.68797
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Affane, M. S.; Bennaceur, H., A weighted arc consistency technique for Max-CSP, (Proc. of the 13th ECAI, Brighton, UK (1998)), 209-213
[2] Bessiere, C.; Regin, J.-C., Arc consistency for general constraint networks: Preliminary results, (Proc. IJCAI-97, Nagoya, Japan (1997)), 398-404
[3] Bessiere, C.; Regin, J.-C., Refining the basic constraint propagation algorithm, (Proc. IJCAI-2001, Seattle, WA (2001)), 309-315
[4] Bistarelli, S.; Fargier, H.; Montanari, U.; Rossi, F.; Schiex, T.; Verfaillie, G., Semiring-based CSPs and valued CSPs: Frameworks, properties and comparison, Constraints, 4, 199-240 (1999) · Zbl 0946.68143
[5] Bistarelli, S.; Montanari, U.; Rossi, F., Semiring-based constraint satisfaction and optimization, J. ACM, 44, 2, 201-236 (1997) · Zbl 0890.68032
[6] Borchers, B.; Furman, J., A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems, J. Combin. Optim, 2, 299-306 (1999) · Zbl 0954.90026
[7] Cabon, B.; de Givry, S.; Lobjois, L.; Schiex, T.; Warners, J., Radio link frequency assignment, Constraints, 4, 79-89 (1999) · Zbl 1020.94500
[8] Cooper, M.; Schiex, T., Arc consistency for soft constraints, Artificial Intelligence, 154, 1-2, 199-227 (2004) · Zbl 1085.68672
[9] Dechter, R., Constraint Processing (2003), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA
[10] Dechter, R.; Kask, K.; Larrosa, J., A general scheme for multiple lower bound computation in constraint optimization, (Proc. CP-2001 (2001)), 346-360 · Zbl 1067.68623
[11] Fargier, H.; Lang, J., Uncertainty in constraint satisfaction problems: A probabilistic approach, (Proc. ECSQARU-93, Granada, Spain (1993))
[12] Freuder, E.; Wallace, R., Partial constraint satisfaction, Artificial Intelligence, 58, 21-70 (1992)
[13] Gilbert, D.; Backofen, R.; Yap, R., Constraints: An International Journal (Special Issue on Bioinformatics), 6, 2-3 (2001)
[14] Larrosa, J., Node and arc consistency in weighted csp, (Proc. 18th AAAI-02, Edmonton, AB (2002)), 48-53
[15] Larrosa, J.; Meseguer, P.; Schiex, T., Maintaining reversible DAC for Max-CSP, Artificial Intelligence, 107, 1, 149-163 (1999) · Zbl 0911.68064
[16] A. Mackworth, Consistency in networks of constraints, Artificial Intelligence 8; A. Mackworth, Consistency in networks of constraints, Artificial Intelligence 8 · Zbl 0341.68061
[17] Meseguer, P.; Sanchez, M., Specializing Russian doll search, (Proc. CP-01, Paphos, Cyprus (2001)), 464-478 · Zbl 1067.68657
[18] Mohr, R.; Masini, G., Good old discrete relaxation, (Proc. ECAI-88, Munich, Germany (1988)), 651-656
[19] Pearl, J., Probabilistic Inference in Intelligent Systems. Networks of Plausible Inference (1988), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA
[20] Rosenfeld, A.; Hummel, R. A.; Zucker, S. W., Scene labeling by relaxation operations, IEEE Trans. Systems Man Cybernet, 6, 6, 173-184 (1976) · Zbl 0335.68070
[21] Rossi, F.; Venable, K. B.; Walsh, T., CP networks: semantics, complexity, approximations and extensions, (Proceedings of the 4th International Workshop on Soft Constraints, Soft 02, Ithaca, NY (2002)), 73-86
[22] Sandholm, T., An algorithm for optimal winner determination in combinatorial auctions, (Proc. IJCAI-99, Stockholm, Sweden (1999)), 542-547
[23] Schiex, T., Possibilistic constraint satisfaction problems or “How to handle soft constraints?”, (Proc. UAI, Stanford, CA (1992)), 268-275
[24] Schiex, T., Arc consistency for soft constraints, (Proc. CP-2000, Singapore (2000)), 411-424 · Zbl 1044.68797
[25] Schiex, T.; Fargier, H.; Verfaillie, G., Valued constraint satisfaction problems: hard and easy problems, (Proc. IJCAI-95, Montréal, Quebec (1995)), 631-637
[26] Shapiro, L.; Haralick, R., Structural descriptions and inexact matching, IEEE Trans. Pattern Anal. Machine Intelligence, 3, 504-519 (1981)
[27] Smith, B., Phase transition and the mushy region in constraint satisfaction, (Proc. ECAI-94, Amsterdam (1994)), 100-104
[28] Snow, P.; Freuder, E., Improved relaxation and search methods for approximate constraint satisfaction with a maximin criterion, (Proc. of the 8th Biennial Conference of the Canadian Society for Computational Studies of Intelligence, Ottawa, ON (1990)), 227-230
[29] Verfaillie, G.; Lemaı̂tre, M.; Schiex, T., Russian doll search, (Proc. AAAI-96, Portland, OR (1996)), 181-187
[30] Wallace, R., Enhancements of branch and bound methods for the maximal constraint satisfaction problem, (Proc. AAAI-96, Portland, OR (1996)), 188-195
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.