Abstract
Over the past few years there has been considerable progress in methods to systematically analyse the complexity of classical (crisp) constraint satisfaction problems with specified constraint types. One very powerful theoretical development in this area links the complexity of a set of classical constraints to a corresponding set of algebraic operations, known as polymorphisms.
In this paper we begin a systematic investigation of the complexity of combinatorial optimisation problems expressed using various forms of soft constraints. We extend the notion of a polymorphism by introducing a more general algebraic operation, which we call a multimorphism. We show that a number of maximal tractable sets of soft constraints, both established and novel, can be characterised by the presence of particular multimorphisms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
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)
Bjäreland, M., Jonsson, P.: Exploiting bipartiteness to identify yet another tractable subclass of CSP. In: Jaffar, J. (ed.) CP 1999. LNCS, vol. 1713, pp. 118–128. Springer, Heidelberg (1999)
Bulatov, A.A.: A dichotomy theorem for constraints on a three-element set. In: Proceedings 43rd IEEE Symposium on Foundations of Computer Science, FOCS 2002, pp. 649–658. IEEE Computer Society, Los Alamitos (2002)
Bulatov, A.A., Krokhin, A.A., Jeavons, P.G.: Constraint satisfaction problems and finite algebras. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 272–282. Springer, Heidelberg (2000)
Bulatov, A.A., Krokhin, A.A., Jeavons, P.G.: The complexity of maximal constraint languages. In: Proceedings 33rd ACM Symposium on Theory of Computing, STOC 2001, pp. 667–674 (2001)
Cohen, D., Cooper, M., Jeavons, P., Krokhin, A.: A tractable class of soft constraints. Technical Report CSD-TR-02-14, Computer Science Department, Royal Holloway, University of London, Egham, Surrey, UK (short version to appear in Proceedings of IJCAI 2003) (December 2002)
Cohen, D., Cooper, M., Jeavons, P., Krokhin, A.: An investigation of the multimorphisms of tractable and intractable classes of valued constraints. Technical Report CSD-TR-03-03, Computer Science Department, Royal Holloway, University of London, Egham, Surrey, UK (2003)
Cooper, M.C., Cohen, D.A., Jeavons, P.G.: Characterising tractable constraints. Artificial Intelligence 65, 347–361 (1994)
Creignou, N., Khanna, S., Sudan, M.: Complexity Classification of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics, Philadelphia, PA, vol. 7 (2001)
Cunningham, W.H.: Minimum cuts, modular functions, and matroid polyhedra. Networks 15(2), 205–215 (1985)
Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM Journal on Computing 23(4), 864–894 (1994)
Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal of Computing 28, 57–104 (1998)
Fleischer, L., Iwata, S.: Improved algorithms for submodular function minimization and submodular flow. In: Proceedings of the 32th Annual ACM Symposium on Theory of Computing, pp. 107–116 (2000)
Fujishige, S., Iwata, S.: Bisubmodular function minimization. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol. 2081, p. 160. Springer, Heidelberg (2001)
Garey, M., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Grötschel, M., Lovasz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169–198 (1981)
Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. Journal of the ACM 48(4), 761–777 (2001)
Jeavons, P.G., Cohen, D.A., Cooper, M.C.: Constraints, consistency and closure. Artificial Intelligence 101(1–2), 251–265 (1998)
Jeavons, P.G., Cohen, D.A., Gyssens, M.: A test for tractability. In: Freuder, E.C. (ed.) CP 1996. LNCS, vol. 1118, pp. 267–281. Springer, Heidelberg (1996)
Jeavons, P.G., Cohen, D.A., Gyssens, M.: Closure properties of constraints. Journal of the ACM 44, 527–548 (1997)
Jeavons, P.G., Cohen, D.A., Gyssens, M.: How to determine the expressive power of constraints. Constraints 4, 113–131 (1999)
Jeavons, P.G., Cohen, D.A., Pearson, J.K.: Constraints and universal algebra. Annals of Mathematics and Artificial Intelligence 24, 51–67 (1998)
Jeavons, P.G., Cooper, M.C.: Tractable constraints on ordered domains. Artificial Intelligence 79(2), 327–339 (1995)
Khatib, L., Morris, P., Morris, R., Rossi, F.: Temporal constraint reasoning with preferences. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI 2001), Seattle, USA, pp. 322–327 (2001)
Kirousis, L.: Fast parallel constraint satisfaction. Artificial Intelligence 64, 147–160 (1993)
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. John Wiley & Sons, Chichester (1988)
Pearson, J.K., Jeavons, P.G.: A survey of tractable constraint satisfaction problems. Technical Report CSD-TR-97-15, Royal Holloway, Univ. of London (1997)
Pöschel, R., Kalužnin, L.A.: Funktionen- und Relationenalgebren. DVW, Berlin (1979)
Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings 10th ACM Symposium on Theory of Computing, STOC 1978, pp. 216–226 (1978)
Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. JCTB: Journal of Combinatorial Theory, Series B 80, 346–355 (2000)
van Hentenryck, P., Deville, Y., Teng, C.-M.: A generic arc-consistency algorithm and its specializations. Artificial Intelligence 57, 291–321 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cohen, D.A., Cooper, M., Jeavons, P., Krokhin, A. (2003). Soft Constraints: Complexity and Multimorphisms. In: Rossi, F. (eds) Principles and Practice of Constraint Programming – CP 2003. CP 2003. Lecture Notes in Computer Science, vol 2833. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45193-8_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-45193-8_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20202-8
Online ISBN: 978-3-540-45193-8
eBook Packages: Springer Book Archive