Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 Introducing global constraints in CHIP
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. The among constraint allows to specify sequencing
constraints in a very concise way. For the first time, the diffn
constraint allows to express and to solve directly multidimensional
placement problems where one has to consider non overlapping
constraints between n-dimensional objects (e.g. rectangles,
parallelepipeds). The cycle constraint 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.