Abstract
This paper describes the design, implementation, and applications of the constraint logic language cc(FD). cc(FD) is a declarative nondeterministic constraint logic language over finite domains based on the cc framework [28], an extension of the CLP scheme [17]. Its constraint solver includes (non-linear) arithmetic constraints over natural numbers which are approximated using domain and interval consistency. The main novelty of cc(FD) is the inclusion of a number of general-purpose combinators, in particular cardinality, constructive disjunction, and blocking implication, in conjunction with new constraint operations such as constraint entailment and generalization. These combinators significantly improve the operational expressiveness, extensibility, and flexibility of CLP languages and allows issues such as the definition of non-primitive constraints and disjunctions to be tackled at the language level. The implementation of cc(FD) (about 40,000 lines of C) includes a WAM-based engine [37], optimal arc-consistency algorithms based on AC-5 [35], and incremental implementation of the combinators. Results on numerous problems, including scheduling, resource allocation, sequencing, packing, and hamiltonian paths are reported and indicate that cc(FD) comes close to procedural languages on a number of combinatorial problems. In addition, a small cc(FD) program was able to find the optimal solution and prove optimality to a famous 10/10 disjunctive scheduling problem [24], which was left open for more than 20 years and finally solved in 1988.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Aggoun and N. Beldiceanu. Extending CHIP To Solve Complex Scheduling and Packing Problems. In Journées Francophones De Programmation Logique, Lille, France, 1992.
M. Bartusch. Optimierung von Netzplaenen mit Anordnungsbeziehungen bei Knappen Betriebsmitteln. PhD thesis, Fakultaet fuer Mathematik und Informatik, Universitaet Passau (F.R.G), 1983.
W. Buttner and H. Simonis. Embedding Boolean Expressions into Logic Programming. Journal of Symbolic Computation, 4:191–205, October 1987.
J. Carlier. Ordonnancement á Constraintes Disjonctives. RAIRO Operations Research, 12(4):333–351, November 1978.
J. Carlier and E. Pinson. Une Méthode Arborescente pour Optimiser la Durée d'un JOB-SHOP. Technical Report ISSN 0294–2755, I.M.A, Angers, 1986.
M. Carlsson. Freeze, Indexing and Other Implemenation Issues on the WAM. In J-L. Lassez, editor, Fourth International Conference on Logic Programming, pages 40–58, Melbourne, Australia, 1987.
J.W. Chinneck, R.A. Goubran, G.M. Karam, and M. Lavoie. A Design Approach for Real-Time Multiprocessor DSP Applications. Report SCE-90-05, Carleton University, Ottawa, Canada, February 1990.
N. Christofides. Graph Theory: An Algorithmic Approach. Academic Press, New York, 1975.
A. Colmerauer. An Introduction to Prolog III. CACM, 28(4):412–418, 1990.
M.C. Costa. Une Etude Pratique de découpes de Panneaux de Bois. RAIRO Recherche Operationnelle, 18(3):211–219, August 1984.
T. Dean and M. Boddy. An Analysis of Time-dependent Planning. In Proceedings of the Seventh National Conference On Artificial Intelligence, pages 49–54, Minneapolis, Minnesota, August 1988.
M. Dincbas, H. Simonis, and P. Van Hentenryck. Solving the Car Sequencing Problem in Constraint Logic Programming. In European Conference on Artificial Intelligence (ECAI-88), Munich, W. Germany, August 1988.
M. Dincbas, H. Simonis, and P. Van Hentenryck. Solving Large Combinatorial Problems in Logic Programming. Journal of Logic Programming, 8(l–2):75–93, January/March 1990.
M. Dincbas, P. Van Hentenryck, H. Simonis, A. Aggoun, T. Graf, and F. Berthier. The Constraint Logic Programming Language CHIP. In Proceedings of the International Conference on Fifth Generation Computer Systems, Tokyo, Japan, December 1988.
T. Graf. Extending Constraint Handling in Logic Programming to Rational Arithmetic. Internal Report, ECRC, Munich, Septembre 1987.
T. Graf, P. Van Hentenryck, C. Pradelles, and L. Zimmer. Simulation of Hybrid Circuits in Constraint Logic Programming. In International Joint Conference on Artificial Intelligence, Detroit, Michigan, August 1989.
J. Jaffar and J-L. Lassez. Constraint Logic Programming. In POPL-87, Munich, FRG, January 1987.
J. Jaffar and S. Michaylov. Methodology and Implementation of a CLP System. In Fourth International Conference on Logic Programming, pages 196–218, Melbourne, Australia, May 1987.
M. Kubale and D. Jackowski. A Generalized Implicit Enumeration Algorithm for Graph Coloring. CACM, 28(4):412–418, 1985.
Marco Lavoie. Task Assignment in a DSP Multiprocessor Environment. Master's Thesis, Department of Systems and Computer Engineering, Carleton University, Ottawa, Ontario, August 1990.
A.K. Mackworth. Consistency in Networks of Relations. Artificial Intelligence, 8(1):99–118, 1977.
M.J. Maher. Logic Semantics for a Class of Committed-Choice Programs. In Fourth International Conference on Logic Programming, pages 858–876, Melbourne, Australia, May 1987.
R. Mohr and T.C. Henderson. Arc and Path Consistency Revisited. Artificial Intelligence, 28:225–233, 1986.
J.F. Muth and G.L. Thompson. Industrial Scheduling. Prentice Hall, Englewood Cliffs, NJ, 1963.
R.G. Parker and R.L. Rardin. Discrete Optimization. Academic Press, London (England), 1988.
B.D. Parrello. CAR WARS: The (Almost) Birth of an Expert System. AI Expert, 3(l):60–64, January 1988.
H.M. Salkin. On the Merit of the Generalized Origin and Restarts in Implicit Enumeration. Opns. Res., 18:549–554, 1970.
V.A. Saraswat. Concurrent Constraint Programming Languages. PhD thesis, Carnegie-Mellon University, 1989.
V.A. Saraswat and M. Rinard. Concurrent Constraint Programming. In Proceedings of Seventeenth ACM Symposium on Principles of Programming Languages, San Francisco, CA, January 1990.
V.A. Saraswat, M. Rinard, and P. Panangaden. Semantic Foundations of Concurrent Constraint Programming. In Proceedings of Ninth ACM Symposium on Principles of Programming Languages, Orlando, FL, January 1991.
P. Van Hentenryck. Constraint Satisfaction in Logic Programming. Logic Programming Series, The MIT Press, Cambridge, MA, 1989.
P. Van Hentenryck. Scheduling and Packing in the Constraint Language cc(FD). Technical Report CS-92-43, CS Department, Brown University, 1992.
P. Van Hentenryck and Y. Deville. The Cardinality Operator: A New Logical Connective and Its Application to Constraint Logic Programming. In Eighth International Conference on Logic Programming (ICLP-91), Paris (France), June 1991. Also to appear in Constraint Logic Programming: Selected Research, The MIT Press, 1992.
P. Van Hentenryck, Y. Deville, M.L. Chen, and C.M. Teng. New Results in Consistency of Networks. Technical report, CS Department, Brown University, 1992. Forthcoming.
P. Van Hentenryck, Y. Deville, and C.M. Teng. A Generic Arc Consistency Algorithm and its Specializations. Artificial Intelligence, 57(2–3), 1992.
P. Van Hentenryck and T. Graf. Standard Forms for Rational Linear Arithmetics in Constraint Logic Programming. Annals of Mathematics and Artificial Intelligence, 5(2–4):303–320, 1992.
D.H.D Warren. An Abstract Prolog Instruction Set. Technical Report 309, SRI, October 1983.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Van Hentenryck, P., Saraswat, V., Deville, Y. (1995). Design, implementation, and evaluation of the constraint language cc(FD). In: Podelski, A. (eds) Constraint Programming: Basics and Trends. TCS School 1994. Lecture Notes in Computer Science, vol 910. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-59155-9_15
Download citation
DOI: https://doi.org/10.1007/3-540-59155-9_15
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-59155-9
Online ISBN: 978-3-540-49200-9
eBook Packages: Springer Book Archive