## Introducing Global Constraints in CHIP## Nicolas Beldiceanu and Evelyne Contejean |

Abstract:The purpose of this paper is to show how the introduction of new primitive constraints (e.g.among, diffn, cycle) over finite domains 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. Theamongconstraint allows to specify sequencing constraints in a very concise way. For the first time, thediffnconstraint allows to express and to solve directly multidimensional placement problems where one has to consider non overlapping constraints betweenn-dimensional objects (e.g. rectangles, parallelepipeds). Thecycleconstraint makes 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 advantage 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 to solve real life problems that were not within reach of constraint technology before.

This document was translated from L^{A}T_{E}X byH^{E}V^{E}A.