Semiring-based constraint satisfaction and optimization

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.

REFERENCES

• 1: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 2: BELLMAN, R. E., AND DREYFUS, S.E. 1962. Applied Dynamic Programming. Princeton University Press, Princeton, N.J.
• 3: Umberto Bertele , Francesco Brioschi, Nonserial Dynamic Programming, Academic Press, Inc., Orlando, FL, 1972
• 4: BISTARELLI, S. 1994. Programmazione con vincoli pesati e ottimizzazione (in Italian). Tech. Rep. ipartmento di Informatica, Universita di Pisa, Pisa, Italy.
• 5: Stefano Bistarelli , Hélène Fargier , Ugo Montanari , Francesca Rossi , Thomas Schiex , Gérard Verfaillie, Semiring-Based CSPs and Valued CSPs: Basic Properties and Comparison, Over-Constrained Systems, p.111-150, January 1996
• 6: 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.
• 7: 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.
• 8: 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.
• 9: DAVEY, B. A., AND PRIESTLY, H. A. 1990. Introductions to Lattices and Order. Cambridge University Press, Cambridge, England. pp. 37-42.
• 10: 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.
• 11: 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.
• 12: R. Dechter , J. Pearl, Network-based heuristics for constraint satisfaction problems, Search in Artificial Intelligence, Springer-Verlag, London, 1988
• 13: 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.
• 14: 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.
• 15: Hélène Fargier , Jérôme Lang, Uncertainty in Constraint Satisfaction Problems: a Probalistic Approach, Proceedings of the European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, p.97-104, November 08-10, 1993
• 16: Eugene C. Freuder, Synthesizing constraint expressions, Communications of the ACM, v.21 n.11, p.958-966, Nov. 1978 [doi>10.1145/359642.359654]
• 17: E. C. Freuder, Backtrack-free and backtrack-bounded search, Search in Artificial Intelligence, Springer-Verlag, London, 1988
• 18: Eugene C. Freuder , Richard J. Wallace, Partial constraint satisfaction, Artificial Intelligence, v.58 n.1-3, p.21-70, Dec. 1992 [doi>10.1016/0004-3702(92)90004-H]
• 19: 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.
• 20: Stefania Gnesi , Ugo Montanari , Alberto Martelli, Dynamic Programming as Graph Searching: An Algebraic Approach, Journal of the ACM (JACM), v.28 n.4, p.737-751, Oct. 1981 [doi>10.1145/322276.322285]
• 21: Marc Gyssens , Peter G. Jeavons , David A. Cohen, Decomposing constraint satisfaction problems using database techniques, Artificial Intelligence, v.66 n.1, p.57-89, March 1994 [doi>10.1016/0004-3702(94)90003-5]
• 22: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• 23: Vipin Kumar, Algorithms for constraint-satisfaction problems: a survey, AI Magazine, v.13 n.1, p.32-44, Spring 1992
• 24: MACKWORTH, A.K. 1977. Consistency in networks of relations. Artif. Int. 8, 1, 99-118.
• 25: MACKWORTH, A. K. 1992. Constraint satisfaction. In Encyclopedia of AI, 2nd ed., vol. 1, S. C. Shapiro, ed. Wiley, New York, pp. 285-293.
• 26: Alan K. Mackworth , Eugene C. Freuder, The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artificial Intelligence, v.25 n.1, p.65-74, Jan. 1985 [doi>10.1016/0004-3702(85)90041-4]
• 27: 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.
• 28: MONTANARI, U. 1974. Networks of constraints: Fundamental properties and application to picture processing. Inf. Sci. 7, 95-132.
• 29: Ugo Montanari , Francesca Rossi, An Efficient Algorithm for the Solution of Hierarchical Networks of Constraints, Proceedings of the 3rd International Workshop on Graph-Grammars and Their Application to Computer Science, p.440-457, December 02-06, 1986
• 30: Ugo Montanari , Francesca Rossi, Constraint relaxation may be perfect, Artificial Intelligence, v.48 n.2, p.143-170, March 1991 [doi>10.1016/0004-3702(91)90059-S]
• 31: MOULIN, H. 1988. Axioms for Cooperative Decision Making. Cambridge University Press, Cambridge, Mass.
• 32: ROSENFELD, A., HUMMEL, R. A., AND ZUCKER, S.W. 1976. Scene labelling by relaxation operations. IEEE Trans. Syst., Man, Cyber 6, 6, 420-433.
• 33: RUTTKAY, ZS. 1994. Fuzzy constraint satisfaction. In Proceedings of the IEEE 3rd International Conference on Fuzzy Systems. IEEE, New York, pp. 1263-1268.
• 34: 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.)
• 35: Thomas Schiex, Possibilistic constraint satisfaction problems or “how to handle soft constraints?”, Proceedings of the eighth conference on Uncertainty in Artificial Intelligence, p.268-275, June 1992, Stanford, California, United States
• 36: 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.
• 37: Prakash P. Shenoy, Valuation-based systems for discrete optimisation, Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, p.385-400, July 27-29, 1990
• 38: Prakash P. Shenoy, Valuation-based systems: a framework for managing uncertainty in expert systems, Fuzzy logic for the management of uncertainty, John Wiley & Sons, Inc., New York, NY, 1992
• 39: Pascal Van Hentenryck, Constraint satisfaction in logic programming, MIT Press, Cambridge, MA, 1989
• 40: ZADEH, L.A. 1965. Fuzzy sets. Inf. Control 8, 338-353.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning

General Terms:
Algorithms, Theory

Keywords:
constraint solving, dynamic programming, local consistency, non-crisp constraint reasoning