Stefano Bistarelli
Ugo Montanari
Skip Abstract Section
Abstract
We introduce a general framework for constraint satisfaction and optimization where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. The framework is based on a semiring structure, where the set of the semiring specifies the values to be associated with each tuple of values of the variable domain, and the two semiring operations (+ and X) model constraint projection and combination respectively. Local consistency algorithms, as usually used for classical CSPs, can be exploited in this general framework as well, provided that certain conditions on the semiring operations are satisfied. We then show how this framework can be used to model both old and new constraint solving and optimization schemes, thus allowing one to both formally justify many informally taken choices in existing schemes, and to prove that local consistency techniques can be used also in newly defined schemes.
- BELLMAN, R.E. 1957. Dynamic Programming. Princeton University Press, Princeton, N.J. Google Scholar
- BELLMAN, R. E., AND DREYFUS, S.E. 1962. Applied Dynamic Programming. Princeton University Press, Princeton, N.J.Google Scholar
- BEa#LE, U., AND BRIOSCHI, F. 1972. Nonserial Dynamic Programming. Academic Press, Orlando, Fla. Google Scholar
- BISTARELLI, S. 1994. Programmazione con vincoli pesati e ottimizzazione (in Italian). Tech. Rep. ipartmento di Informatica, Universita di Pisa, Pisa, Italy.Google Scholar
- BISTARELLI, S., FARGmR, H., MONTANARI, U., ROSSI, F., SCHmX, T., AND VERFAmLE, G. 1996. Semiring-based CSPs and valued CSPs: Basic properties and comparison. In Over-Constrained Systems, M. Jampel, ed. Lecture Notes in Computer Science, Vol. 1106. Springer-Verlag, New York. Google Scholar
- BISTARELLI, S., MONTANARI, U., AND ROSSI, F. 1995. Constraint solving over semirings. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI95). Morgan- Kaufmann, San Mateo, Calif., pp. 624-630. Google Scholar
- BORNING, A., MAHER, M., MARTINDALE, A., AND WILSON, M. 1989. Constraint hierarchies and logic programming. In Proceeding of the 6th International Conference on Logic Programming. MIT Press, Cambridge, Mass., pp. 149-164.Google Scholar
- COUSOT, P. 1977. Asynchronous iterative methods for solving a fixed point system of monotone equations in a complete lattice. Tech. Rep. R.R.88. Institut National Polytechnique de Grenoble, Grenoble, Switzerland.Google Scholar
- DAVEY, B. A., AND PRIESTLY, H. A. 1990. Introductions to Lattices and Order. Cambridge University Press, Cambridge, England. pp. 37-42.Google Scholar
- DECHTER R., AND DECHTER, A. 1988. Brief maintenance in dynamic constraint networks. In Proceedings of the AA/tI88. Morgan-Kaufmann, San Mateo, Calif., pp. 37-42.Google Scholar
- DECHTER, R., DECHTER, A., AND PEARL, J. 1990. Optimization in constraint networks. In Influence Diagrams, Belief Nets and Decision Analysis, R. M. Oliver and J. Q. Smith, eds. Wiley, New York, pp. 411-425.Google Scholar
- DECHTER, R., AND PEARL, J. 1988a. Network-based heuristics for constraint-satisfaction problems. In Search in Artificial Intelligence, Kanal and Kumar, eds. Springer-Verlag, New York, pp. 370-425. Google Scholar
- DECHTER, R., AND PEARL, J. 1988b. Tree-clustering schemes for constraint processing. In Proceedings of the AA/tI88. Morgan-Kaufmann, San Mateo, Calif., pp. 150-154.Google Scholar
- DUBOIS, D., FARGIER, n., AND PRADE, n. 1993. The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction. In Proceedings of the IEEE International Conference on Fuzzy Systems. IEEE, New York, pp. 1131-1136.Google Scholar
- FARGIER, n., AND LANG, J. 1993. Uncertainty in constraint satisfaction problems: A probabilistic approach. In Proceedings of the European Conference on Symbolic and Qualitative Approaches to Reasoning and Uncertainty (ESQUARU). Lecture Notes in Computer Science, vol. 747. Springer- Verlag, New York, pp. 97-104. Google Scholar
- FREUDER, E.C. 1978. Synthesizing constraint expressions. Commun. ACM21, 11 (Nov.), 958-965. Google Scholar
- FREUDER, E. C. 1988. Backtrack-free and backtrack-bounded search. In Search in Artificial Intelligence, Kanal and Kumar, eds. Springer-Verlag, New York, pp. 343-369. Google Scholar
- FREUDER, E. C., AND WALLACE, R.J. 1992. Partial constraint satisfaction. AI J. 58, 21-70. Google Scholar
- GIACOBAZZI, R., DEBRAY, S. K., AND LEVI, G. 1992. A generalized semantics for constraint logic programs. In Proceedings of Fifth Generation Computer Systems (FGCS92). ICOT, Tokyo, Japan, pp. 581-591.Google Scholar
- GNESI, S., MONTANARI, U., AND MARTELLI, A. 1981. Dynamic programming as graph searching: An algebraic approach. J. ACM 28, 4 (Oct.), 737-751. Google Scholar
- GYSSENS, M., JEAVONS, P. G., AND COHEN, D. A. 1994. Decomposing constraint satisfaction problems using database techniques. Artif. Int. 66, 1, 57-89. Google Scholar
- JAFFAR, J., AND LASSEZ, J.L. 1987. Constraint logic programming. In Proceedings of Principles of Programming Languages (Munich, West Germany, Jan. 21-23). ACM, New York, pp. 111-119. Google Scholar
- KUMAR, V. 1992. Algorithms for constraint satisfaction problems: A survey. AI Mag. 13, 1, 32-44. Google Scholar
- MACKWORTH, A.K. 1977. Consistency in networks of relations. Artif. Int. 8, 1, 99-118.Google Scholar
- MACKWORTH, A. K. 1992. Constraint satisfaction. In Encyclopedia of AI, 2nd ed., vol. 1, S. C. Shapiro, ed. Wiley, New York, pp. 285-293.Google Scholar
- MACKWORTH, A. K., AND FREUDER, E. C. 1984. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems./trtif. Int. 25, 65-74. Google Scholar
- MARTELLI, A., AND MONTANARI, U. 1972. Nonserial dynamic programming: On the optimal strategy of variable elimination for the rectangular lattice. J. Math. Anal./tppl. 40, 226-242.Google Scholar
- MONTANARI, U. 1974. Networks of constraints: Fundamental properties and application to picture processing. Inf. Sci. 7, 95-132.Google Scholar
- MONTANARI, U., AND ROSSI, F. 1986. An efficient algorithm for the solution of hierarchical networks of constraints. In Proceedings of the International Workshop on Graph Grammars and Their Application to Computer Science. Lecture Notes in Computer Science, vol. 291. Springer-Verlag, New York, pp. 440-457. Google Scholar
- MONTANARI, U., AND ROSSI, F. 1991. Constraint relaxation may be perfect. AI J. 48, 143-170. Google Scholar
- MOULIN, H. 1988. Axioms for Cooperative Decision Making. Cambridge University Press, Cambridge, Mass.Google Scholar
- ROSENFELD, A., HUMMEL, R. A., AND ZUCKER, S.W. 1976. Scene labelling by relaxation operations. IEEE Trans. Syst., Man, Cyber 6, 6, 420-433.Google Scholar
- RUTTKAY, ZS. 1994. Fuzzy constraint satisfaction. In Proceedings of the IEEE 3rd International Conference on Fuzzy Systems. IEEE, New York, pp. 1263-1268.Google Scholar
- RossI, F., AND SPERDUTI, A. 1996. Learning solution preferences in constraint problems. In Proceedings of the International Workshop on Non-Standard Constraint Processing at EC/tI96. Taylor and Francis publishers. (A longer version will appear in J. Exp. Theor. Artif Int.)Google Scholar
- SCHIEX, f. 1992. Possibilistic constraint satisfaction problems or "how to handle soft constraints?" In Proceedings of the 8th Conference of Uncertainty in Artificial Intelligence. pp. 269-275. Google Scholar
- SCHIEX, T., FARGIER, H., AND VERFAILLE, G. 1995. Valued constraint satisfaction problems: Hard and easy problems. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI95). Morgan-Kaufmann, San Mateo, Calif., pp. 631-637. Google Scholar
- SHENOY, P. 1991. Valuation-based systems for discrete optimization. In Uncertainty in Artificial Intelligence, L. N. Kanal, P. P. Bonissone, M. Henrion, and J. F. Lemayer, eds. Elsevier Science, Amsterdam, The Netherlands. Google Scholar
- SHENOY, P. 1994. Valuation-based systems: A framework for managing uncertainty in expert systems. In Fuzzy Logic for the Management of Uncertainty, L. Zadeh and J. Kacprzyk, eds. Wiley, New York, pp. 83-104. Google Scholar
- VAN HENTENRYCK, P. 1989. Constraint Satisfaction in Logic Programming. MIT Press, Cambridge, Mass. Google Scholar
- ZADEH, L.A. 1965. Fuzzy sets. Inf. Control 8, 338-353.Google Scholar
Index Terms
- Semiring-based constraint satisfaction and optimization
Recommendations
Relaxations of semiring constraint satisfaction problems
The Semiring Constraint Satisfaction Problem (SCSP) framework is a popular approach for the representation of partial constraint satisfaction problems. In this framework preferences can be associated with tuples of values of the variable domains. ...
Soft constraint abstraction based on semiring homomorphism
The semiring-based constraint satisfaction problems (semiring CSPs), proposed by Bistarelli, Montanari and Rossi [S. Bistarelli, U. Montanari, F. Rossi, Semiring-based constraints solving and optimization, Journal of the ACM 44 (2) (1997) 201-236], is a ...
Constraint Hierarchies as Semiring-Based CSPs
ICTAI '09: Proceedings of the 2009 21st IEEE International Conference on Tools with Artificial IntelligenceConstraints provide an effective means for the high-level modeling and reasoning of various problems. In particular, soft constraints are useful since they treat over-constrained problems that naturally arise in real-life applications. Therefore, ...
Comments