INTRODUCING GLOBAL CONSTRAINTS IN CHIP

被引:155
作者
BELDICEANU, N [1 ]
CONTEJEAN, E [1 ]
机构
[1] UNIV PARIS 11, LRI, CNRS, URA 410, F-91405 ORSAY, FRANCE
关键词
CONSTRAINT PROGRAMMING; MULTIDIMENSIONAL PLACEMENT; SCHEDULING; VEHICLE ROUTING;
D O I
10.1016/0895-7177(94)90127-9
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
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 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.
引用
收藏
页码:97 / 123
页数:27
相关论文
共 21 条
[1]   EXTENDING CHIP IN ORDER TO SOLVE COMPLEX SCHEDULING AND PLACEMENT PROBLEMS [J].
AGGOUN, A ;
BELDICEANU, N .
MATHEMATICAL AND COMPUTER MODELLING, 1993, 17 (07) :57-73
[2]  
AGGOUN A, 1991, 8TH P INT C LOG PROG, P775
[3]  
Baker K., 1974, INTRO SEQUENCING SCH
[4]  
BILLIONNET A, 1989, TSI-TECH SCI INF, V8, P307
[5]  
Coffin S.T, 1990, PUZZLING WORLD POLYH
[6]   TEMPORAL CONSTRAINT NETWORKS [J].
DECHTER, R ;
MEIRI, I ;
PEARL, J .
ARTIFICIAL INTELLIGENCE, 1991, 49 (1-3) :61-95
[7]  
DEJAX P, 1990, RAIRO OPERATIONS RES, V24, P217
[8]  
DINCBAS M, 1988, AUG EUR C ART INT EC, P290
[9]  
DINCBAS M, 1988, 5TH P INT C GEN COMP, P693
[10]  
du Verdier F., 1991, Eleventh International Conference. Expert Systems and their Applications Conference, P297