Abstract
Existing constraint programming systems offer a fixed set of inference engines implementing search strategies such as single, all, and best solution search. This is unfortunate, since new engines cannot be integrated by the user. The paper presents first-class computation spaces as abstractions with which the user can program inference engines at a high level. Using computation spaces, the paper covers several inference engines ranging from standard search strategies to techniques new to constraint programming, including limited discrepancy search, visual search, and saturation. Saturation is an inference method for tautologychecking used in industrial practice. Computation spaces have shown their practicability in the constraint programming system Oz.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Abderrahamane Aggoun, David Chan, Pierre Dufresne, Eamon Falvey, Hugh Grant, Alexander Herold, Geoffrey Macartney, Micha Meier, David Miller, Shyam Mudambi, Bruno Perez, Emmanuel Van Rossum, Joachim Schimpf, Periklis Andreas Tsahageas, and Dominique Henry de Villeneuve. ECLiPSe 3.5. User manual, European Computer Industry Research Centre (ECRC), Munich, Germany, December 1995.
Philippe Codognet and Daniel Diaz. Compiling constraints in clp (FD). The Journal of Logic Programming, 27(3):185–226, June 1996.
James M. Crawford. An approach to resource constrained project scheduling. In George F. Luger, editor, Proceedings of the 1995 Artificial Intelligence and Manufacturing Research Planning Workshop, Albuquerque, NM, USA, 1996. The AAAI Press.
Mehmet Dincbas, Pascal Van Hentenryck, Helmut Simonis, Abderrahamane Aggoun, Thomas Graf, and F. Berthier. The constraint logic programming language CHIP. In Proceedings of the International Conference on Fifth Generation Computer Systems FGCS-88 , pages 693–702, Tokyo, Japan, December 1988.
John Harrison. Stållmarck's algorithm as a HOL derived rule. In Joakim von Wright, Jim Grundy, and John Harrison, editors, Theorem Proving in Higher Order Logics: 9th International Conference, TPHOLs'96, volume 1125 of Lecture Notes in Computer Science, pages 221–234, Turku, Finland, August 1996. Springer-Verlag.
William D. Harvey and Matthew L. Ginsberg. Limited discrepancy search. In Chris S. Mellish, editor, Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, pages 607–615, Montreal, Canada, August 1995. Morgan Kaufmann Publishers.
Martin Henz, Martin Müller, Christian Schulte, and Jörg Würtz. The Oz standard modules. DFKI Oz documentation series, German Research Center for Artificial Intelligence (DFKI), Stuhlsatzenhausweg 3, D-66123 Saarbrücken, Germany, 1997.
Martin Henz, Gert Smolka, and Jörg Würtz. Object-oriented concurrent constraint programming in Oz. In Vijay Saraswat and Pascal Van Hentenryck, editors, Principles and Practice of Constraint Programming, pages 29–48. The MIT Press, Cambridge, MA, USA, 1995.
ILOG. ILOG Solver: User manual, July 1996. Version 3.2.
Richard E. Korf. Depth-first iterative deepening: An optimal admissible tree search. Artificial Intelligence, 27(1):97–109, 1985.
Christian Schulte. Oz Explorer: A visual constraint programming tool. In Lee Naish, editor, Proceedings of the Fourteenth International Conference on Logic Programming, pages 286–300, Leuven, Belgium, July 1997. The MIT Press.
Christian Schulte and Gert Smolka. Encapsulated search in higher-order concurrent constraint programming. In Maurice Bruynooghe, editor, Logic Programming: Proceedings of the 1994 International Symposium, pages 505–520, Ithaca, NY, USA, November 1994. The MIT Press.
Gert Smolka. The Oz programming model. In Jan van Leeuwen, editor, Computer Science Today, volume 1000 of Lecture Notes in Computer Science, pages 324–343. Springer-Verlag, Berlin, 1995.
Gunnar Stålmarck. A system for determining propositional logic theorems by applying values and rules to triplets that are generated from a formula. U.S. patent 5 276 897, 1994. Also as Swedish patent 467 076, 1991.
Joachim Paul Walser. Feasible cellular frequency assignment using constraint programming abstractions. In Proceedings of the Workshop on Constraint Programming Applications, in conjunction with the Second International Conference on Principles and Practice of Constraint Programming (CP96), Cambridge, MA, USA, August 1996.
Jörg Würtz. Oz Scheduler: A workbench for scheduling problems. In Proceedings of the 8th IEEE International Conference on Tools with Artificial Intelligence, pages 132–139, Toulouse, France, November 1996. IEEE Computer Society Press.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schulte, C. (1997). Programming constraint inference engines. In: Smolka, G. (eds) Principles and Practice of Constraint Programming-CP97. CP 1997. Lecture Notes in Computer Science, vol 1330. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0017464
Download citation
DOI: https://doi.org/10.1007/BFb0017464
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63753-0
Online ISBN: 978-3-540-69642-1
eBook Packages: Springer Book Archive