×

zbMATH — the first resource for mathematics

Introducing global constraints in CHIP. (English) Zbl 0816.68048
Summary: The purpose of this paper is to show how the introduction of new primitive constraints (e.g., among, diffn, cycle) over finite domain in the constraint logic programming system CHIP result in finding very rapidly good solutions for a large class of difficult sequencing, scheduling, geometrical placement and vehicle routing problems. The among constraint allows us to specify sequencing constraints in a very concise way. For the first time, the diffn constraint allows us to express and to solve directly multi-dimensional placement problems, where one has to consider nonoverlapping constraints between \(n\)-dimensional objects (e.g., rectangles, parallelepipeds). The cycle constraint makes it possible to specify a wide range of graph partitioning problems that could not yet be expressed by using current constraint logic programming languages. One of the main advantages of all these new primitives is to take into account more globally a set of elementary constraints. Finally, we point out that all the previous primitive constraints enhance the power of the CHIP system significantly, allowing us to solve real life problems that were not within reach of constraint technology before.

MSC:
68N17 Logic programming
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Software:
CHIP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Dincbas, M.; Van Hentenryck, P.; Simonis, H.; Aggoun, A.; Graf, T.; Berthier, F., The constraint logic programming language CHIP, Tokyo, Proc. int. conf. on fifth generation computer systems FGCS-88, 693-702, (1988)
[2] Aggoun, A.; Beldiceanu, N., Overview of the CHIP compiler system, Paris, France, 8^th international conference on logic programming, 775-789, (June 1991)
[3] Jaffar, J.; Lassez, J.-L., Constraint logic programming, Munich, Germany, Proc. 14^th ACM symp. on principles of programming language, (1987)
[4] Jaffar, J.; Maher, M.J., Constraint logic programming: A survey, Journal of logic programming, 19/20, 503-581, (May/July 1994)
[5] Dechter, R.; Meiri, I.; Pearl, J., Temporal constraint networks, Artificial intelligence, 49, 61-95, (1991) · Zbl 0737.68070
[6] Baker, K.R., Introduction to sequencing and scheduling, (1974), Wiley
[7] Dyckhoff, H., A typology of cutting and packing problems, European journal of operational research, 44, 145-159, (1990) · Zbl 0684.90076
[8] du Verdier, F.; Tsang, J.P., Un raisonnement spatial par propagation de contraintes, (), 297-314
[9] Dejax, P.; Desrochers, M.; Haouari, M., LES problèmes de tournées avec contraintes de fenêtres de temps, l’état de l’art, RAIRO operations research, 24, 3, 217-244, (1990) · Zbl 0704.90045
[10] Dincbas, M.; Simonis, H.; Van Hentenryck, P., Solving the car-sequencing problem in constraint logic programming, Munich, Germany, European conference on artificial intelligence (ECAI-88), 290-295, (August 1988)
[11] Coffin, S.T., The puzzling world of polyhedral dissections, (1990), Oxford University Press
[12] Kung, S.Y.; Whitehouse, H.J.; Kailath, T., VLSI and modern signal processing, (1985), Prentice-Hall
[13] Aggoun, A.; Beldiceanu, N., Extending CHIP in order to solve complex scheduling and placement problems, Mathl. comput. modelling, 17, 7, 57-73, (1993)
[14] Dincbas, M.; Van Hentenryck, P.; Simonis, H.; Aggoun, A.; Graf, T., Applications of CHIP to industrial and engineering problems, Tullahoma, TN, First int. conf. on industrial and engineering applications of artificial intelligence and expert systems, (June 1988)
[15] Tokuyama, T.; Asano, T.; Tsukiyama, S., A dynamic algorithm for placing rectangles without overlapping, Journal of information processing, 14, 1, 30-35, (1991) · Zbl 0764.68182
[16] Billionnet, A.; Costa, M.C.; Sutter, A., LES problèmes de placement dans LES systèmes distribués, Technique et science informatiques, 8, 4, 307-337, (1989)
[17] Li, K.; Cheng, K., On three-dimensional packing, SIAM J. comput., 19, 5, 847-867, (October 1990)
[18] Gehring, H.; Menschner, K.; Meyer, M., A computer-based heuristic for packing pooled shipment containers, European journal of operational research, 44, 277-288, (1990) · Zbl 0684.90084
[19] Sutherland, I.E., Micropipelines, Communications of ACM, 32, 6, (June 1989)
[20] Graham, R.L.; Knuth, D.E.; Patashnik, O., Concrete mathematics, a foundation for computer science, (1989), Addison-Wesley · Zbl 0668.00003
[21] Garey, M.R.; Johnson, D.S., Computers and intractability. A guide to the theory of NP-completeness, (1979), Freeman and Co · Zbl 0411.68039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.