| 1. |
- Beldiceanu, Nicolas, et al.
(författare)
-
A Generic Geometrical Constraint Kernel in Space and Time for Handling Polymorphic k-Dimensional Objects
- 2007. - 1
-
Konferensbidrag (refereegranskat)abstract
- This paper introduces a geometrical constraint kernel for handling the location in space and time of polymorphic k-dimensional objects subject to various geometrical and time constraints. The constraint kernel is generic in the sense that one of its parameters is a set of constraints on subsets of the objects. These constraints are handled globally by the kernel. We first illustrate how to model several placement problems with the constraint kernel. We then explain how new constraints can be introduced and plugged into the kernel. Based on these interfaces, we develop a generic k-dimensional lexicographic sweep algorithm for filtering the attributes of an object (i.e., its shape and the coordinates of its origin as well as its start, duration and end in time) according to all constraints where the object occurs. Experiments involving up to hundreds of thousands of objects and 1 million integer variables are provided in 2, 3 and 4 dimensions, both for simple shapes (i.e., rectangles, parallelepipeds) and for more complex shapes.
|
|
| 2. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Graph Invariants as Necessary Conditions for Global Constraints
- 2005. - 1
-
Ingår i: CP'2005, Principles and Practice of Constraint Programming, LNCS. - : Swedish Institute of Computer Science. ; 3709, s. 92-106
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- This report presents a database of about 200 graph invariants for deriving systematically necessary conditions from the graph properties based representation of global constraints. This scheme is based on invariants on the graph characteristics used in the description of a global constraint. A SICStus Prolog implementation based on arithmetic and logical constraints as well as on indexicals is available.
|
|
| 3. |
- Ågren, Magnus, et al.
(författare)
-
Six ways of integrating symmetries within non-overlapping constraints
- 2009. - 1
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- This report introduces six ways for handling a chain of lexicographic ordering constraint between the origins of identical orthotopes (e.g., rectangles, boxes, hyper-rectangles) subject to the fact that they should not pairwise overlap. While the first two ways deal with the integration of a chain of lexicographic ordering constraint within a generic geometric constraint kernel, the four latter ways deal with the conjunction of a chain of lexicographic ordering constraint and a non-overlapping or a cumulative constraint. Experiments on academic two and three dimensional placement problems as well as on industrial problems show the benefit of such a strong integration of symmetry breaking constraints and non-overlapping ones.
|
|
| 4. |
- Ågren, Magnus, et al.
(författare)
-
Six ways of integrating symmetries within non-overlapping constraints
- 2009. - 1
-
Konferensbidrag (refereegranskat)abstract
- This paper introduces six ways for handling a chain of lexicographic ordering (lex-chain) constraint between the origins of identical orthotopes (e.g., rectangles, boxes, hyper-rectangles) subject to the fact that they should not pairwise overlap. While the first two ways deal with the integration of a lex-chain constraint within a generic geometric constraint kernel, the four latter ways deal with the conjunction of a lex-chain constraint and a non-overlapping or a cumulative constraint. Experiments on academic two and three dimensional placement problems as well as on industrial problems show the benefit of such a strong integration of symmetry breaking constraints and non-overlapping ones.
|
|
