Basic Techniques for Creating an Efficient CSP Solver

Published in Volume XVII, 2007, pages 83-112

Authors: C. Frăsinaru

Abstract

Many computationally difficult problems from areas like planning and scheduling are easily modelled as constraint satisfaction problems (CSP). In order to have an uniform practical approach of these, a new programming paradigm emerged in the form of constraint programming, providing the opportunity of having declarative descriptions of CSP instances and also obtaining their solutions in reasonable computational time.

Full Text (PDF)

References

[1] K. Apt. Principles of constraint programming. Cambridge University Press, 2003.

[2] R. Bartak. On-line guide to constraint programming. http://kti.ms.mff.cuni.cz/bartak/constraints/index.html.

[3] S. Bistarelli. Semirings for Soft Constraint Solving and Programming. Springer, 2004.

[4] Y. Caseau and F. Laburthe. Palm. http://www.e-constraints.net/palm.

[5] R. Dechter. Constraint Processing. Morgan Kaufmann, 2003.

[6] E. C. Freuder. Synthesizing constraint expressions. Communications of the ACM, 21(11):958-966, 1978.

[7] E. C. Freuder. Partial constraint satisfaction. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, IJCAI-89, Detroit, Michigan, USA, pages 278-283, 1989.

[8] C. Frasinaru. Omnics. http://omnics.sourceforge.net.

[9] C. Frasinaru. Curs practic de Java. Matrix Rom Bucuresti, 2005.

[10] E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley Professional, 1995.

[11] M. Gavanelli, E. Lamma, P. Mello, and M. Milano. Performance measurement of interactive CSP search algorithms. In Giornata di Lavoro RCRA su “Analisi sperimentale di algoritmi per l’Intelligenza Artificiale”, Rome, Italy, Dec 16 1999.

[12] Ilog. Ilog solver. http://www.ilog.com.

[13] Koalog. Koalog constraint solver tutorial. http://www.koalog.com.

[14] F. Laburthe and N. Jussien. Choco. http://choco.sourceforge.net.

[15] E. Lamma, P. Mello, M. Milano, R. Cucchiara, M. Gavanelli, and M. Piccardi. Constraint propagation and value acquisition: Why we should do it interactively. In IJCAI, pages 468-477, 1999.

[16] J.-L. Lauriere. A language and a program for stating and solving combinatorial problems. Artificial Intelligence. An International Journal, 10(1):29-127, 1978.

[17] A. K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8(1):99-118, 1977.

[18] U. Monatanari. Networks of constraints: Fundamental properties and application to picture processing. Information Science, 7(2):95-132, 1974.

[19] P. Boizumault N. Jussien, R.Debruyne. Mantaining arc-consistency within dynamic backtracking. In Sixth international conference on principles and practice of constraint programming (CP’2000), 2000.

[20] J.-C. Regin. Global constraints. First International Summer School on Constraint Programming Acquafredda di Maratea – Italy, September 11-15 2005.

[21] F. Rossi, P. van Beek, and T. Walsh (editors). Handbook of Constraint Programming. Elsevier, 2006.

[22] T. Schiex. Soft constraint processing. First International Summer School on Constraint Programming, July 2005.

[23] M. Sergot. A query-the-user facility of logic programming. In In Degano, P., Sandwell, E., eds.: Integrated Interactive Computer Systems, North Holland, pages 27-41, 1983.

[24] G. Verfaille, T. Schiex, H. Fargier. Valued constrained satisfaction problems: hard and easy problems. Proc. of the 14th IJCAI, pages 631-637, 1995.

[25] E. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993.

[26] J. W.Cooper. The Design Patterns Java Companion. Addison-Wesley, 1998

Bibtex

@article{sacscuza:frasinaru2007btfcaecs,
  title={Basic Techniques for Creating an Efficient CSP Solver},
  author={C. Fr{u a}sinaru},
  journal={Scientific Annals of Computer Science},
  volume={17},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2007},
  pages={83--112},
  publisher={``A.I. Cuza'' University Press}
}