Introducing global constraints in CHIP
Introducing global constraints in CHIP
复制标题
DOI：
10.1016/0895-7177(94)90127-9
复制
发表时间：
1994-12
影响因子：
--
通讯作者：
Nicolas Beldiceanu;Évelyne Contejean
中科院分区：
文献类型：
--
作者：
Nicolas Beldiceanu;Évelyne Contejean
本文的目的是展示如何引入新的原始约束（例如，其中，diffn，cycle）在有限域上的约束逻辑编程系统CHIP的结果是非常迅速地找到了一个很大的一类困难的排序，调度，几何布局和车辆路径问题的好的解决方案。该约束允许我们以一种非常简洁的方式指定排序约束。第一次，thediff约束允许我们直接表达和解决多维放置问题，其中必须考虑n维对象之间的非重叠约束（例如，矩形、平行六面体）。Thecycleconstraint使得它可以指定一个广泛的图形划分问题，还不能通过使用当前的约束逻辑编程语言表示。所有这些新原语的主要优点之一是考虑到更全球性的一组基本约束。最后，我们指出，所有以前的原始约束显着增强的权力的CHIP系统，使我们能够解决真实的生活中的问题，约束技术的范围内之前。
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 us to specify sequencing constraints in a very concise way. For the first time, thediffnconstraint allows us to express and to solve directly multi-dimensional placement problems, where one has to consider nonoverlapping constraints betweenn-dimensional objects (e.g., rectangles, parallelepipeds). Thecycleconstraint 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.