×

Which soft constraints do you prefer? (English) Zbl 1347.68197

Roşu, Grigore (ed.), Proceedings of the 7th international workshop on rewriting logic and its applications (WRLA 2008), Budapest, Hungary, March 29–30, 2008. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 238, No. 3, 189-205 (2009).
Summary: Soft constraints are gaining popularity in diverse areas such as orchestration of Web services or optimization of scheduling decisions. However, current approaches to soft constraints preclude them from modelling certain decision problems with multiple preference criteria. We propose a new approach to soft constraints which allows a natural expression of these problems, describe an implementation in the rewriting logic system Maude, and prove its correctness.
For the entire collection see [Zbl 1279.68017].

MSC:

68Q42 Grammars and rewriting systems
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Software:

Cassowary; PAGODA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andréka, Hajnal; Ryan, Mark; Schobbens, Pierre-Yves, Operators and laws for combining preference relations, J. Log. Comput., 12, 1, 13-53 (2002) · Zbl 1008.91027
[2] Badros, Greg J.; Borning, Alan; Stuckey, Peter J., The cassowary linear arithmetic constraint solving algorithm, ACM Trans. Comput.-Hum. Interact., 8, 4, 267-306 (2001)
[3] Bistarelli, Stefano; Frühwirth, Thom W.; Marte, Michael, Soft constraint propagation and solving in chrs., (SAC (2002), ACM), 1-5
[4] Bistarelli, Stefano; Gadducci, Fabio, Enhancing constraints manipulation in semiring-based formalisms, (Brewka, G.; Coradeschi, S.; Perini, A.; Traverso, P., Proceedings of ECAI 2006. Proceedings of ECAI 2006, 17th European Conference on Artificial Intelligence. Proceedings of ECAI 2006. Proceedings of ECAI 2006, 17th European Conference on Artificial Intelligence, Frontiers in Artificial Intelligence and Applications, volume 141 (2006), IOS Press), 63-67
[5] Bistarelli, Stefano; Montanari, Ugo; Rossi, Francesca, Semiring-based constraint satisfaction and optimization, J. ACM, 44, 2, 201-236 (1997) · Zbl 0890.68032
[6] Bistarelli, Stefano; Montanari, Ugo; Rossi, Francesca, Soft concurrent constraint programming, ACM Trans. Comput. Log., 7, 3, 563-589 (2006) · Zbl 1367.68315
[7] Bistarelli, Stefano; Pini, Maria Silvia; Rossi, Francesca; Venable, Kristen Brent, Bipolar preference problems: Framework, properties and solving techniques, (Azevedo, Francisco; Barahona, Pedro; Fages, François; Rossi, Francesca, CSCLP. CSCLP, Lecture Notes in Computer Science, volume 4651 (2006), Springer), 78-92 · Zbl 1176.68196
[8] Bistarelli, Stefano; Pini, Maria Silvia; Rossi, Francesca; Venable, Kristen Brent, Uncertainty in bipolar preference problems, (Bessiere, Christian, CP. CP, Lecture Notes in Computer Science, volume 4741 (2007), Springer), 782-789 · Zbl 1176.68196
[9] Borning, Alan; Freeman-Benson, Bjørn N.; Wilson, Molly, Constraint hierarchies, Lisp and Symbolic Computation, 5, 3, 223-270 (1992) · Zbl 0942.68515
[10] Borning, Alan; Freeman-Benson, Bjørn N.; Wilson, Molly, Constraint hierarchies, (Jampel, Michael; Freuder, Eugene C.; Maher, Michael J., Over-Constrained Systems. Over-Constrained Systems, Lecture Notes in Computer Science, volume 1106 (1995), Springer), 23-62 · Zbl 0942.68515
[11] Bourbaki, Nicolas, Algebra I, Chapters 1-3, Élements de mathématique (1989), Springer, English · Zbl 0673.00001
[12] Bourbaki, Nicolas, Algebra II, Chapters 4-7, Élements de mathématique (1990), Springer, English · Zbl 1017.12001
[13] De Nicola, Rocco; Ferrari, Gianluigi; Montanari, Ugo; Pugliese, Rosario; Tuosto, Emilio, A Basic Calculus for Modelling Service Level Agreements, (Jacquet, Jean-Marie; Picco, Gian Pietro, International Conference on Coordination Models and Languages. International Conference on Coordination Models and Languages, Namur (Belgium). International Conference on Coordination Models and Languages. International Conference on Coordination Models and Languages, Namur (Belgium), LNCS, volume 3454 (April 2005), Springer), 33-48
[14] Delgado, Alberto; Olarte, Carlos Alberto; Pérez, Jorge Andrés; Rueda, Camilo, Implementing semiring-based constraints using mozart, (Van Roy, Peter, MOZ. MOZ, Lecture Notes in Computer Science, volume 3389 (2004), Springer), 224-236
[15] Georget, Yan; Codognet, Philippe, Compiling semiring-based constraints with clp (fd, s), (Maher, Michael J.; Puget, Jean-Francois, CP. CP, Lecture Notes in Computer Science, volume 1520 (1998), Springer), 205-219
[16] Harvey, Warwick; Stuckey, Peter J.; Borning, Alan, Fourier elimination for compiling constraint hierarchies, Constraints, 7, 2, 199-219 (2002) · Zbl 1018.68020
[17] Keeney, R. L.; Raiffa, H., Decisions with Multiple Objectives: Preferences and Value Trade-offs (1993), Cambridge University Press: Cambridge University Press Cambridge
[18] Rudová, Hana, Soft clp (fd), (Russell, Ingrid; Haller, Susan M., FLAIRS Conference (2003), AAAI Press), 202-207
[19] Sannella, Michael; Maloney, John; Freeman-Benson, Bjørn N.; Borning, Alan, Multi-way versus one-way constraints in user interfaces: Experience with the deltablue algorithm, Softw., Pract. Exper., 23, 5, 529-566 (1993)
[20] Wirsing, Martin; Clark, Allan; Gilmore, Stephen; Hölzl, Matthias; Knapp, Alexander; Koch, Nora; Schroeder, Andreas, Semantic-Based Development of Service-Oriented Systems, (Najn, E.; etal., Proc. 26th IFIP WG 6.1 Internat. Conf. on Formal Methods for Networked and Distributed Systems (FORTE’06). Proc. 26th IFIP WG 6.1 Internat. Conf. on Formal Methods for Networked and Distributed Systems (FORTE’06), Paris, France. Proc. 26th IFIP WG 6.1 Internat. Conf. on Formal Methods for Networked and Distributed Systems (FORTE’06). Proc. 26th IFIP WG 6.1 Internat. Conf. on Formal Methods for Networked and Distributed Systems (FORTE’06), Paris, France, LNCS, volume 4229 (2006), Springer), 24-45
[21] Martin Wirsing, Grit Denker, Carolyn Talcott, Andy Poggio, and Linda Briesemeister. A rewriting logic framework for soft constraints. In WRLA 2006, 6th International Workshop on Rewriting Logic and its Applications; Martin Wirsing, Grit Denker, Carolyn Talcott, Andy Poggio, and Linda Briesemeister. A rewriting logic framework for soft constraints. In WRLA 2006, 6th International Workshop on Rewriting Logic and its Applications · Zbl 1279.68124
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.