Holds if, for each pair of objects , , and do not overlap with respect to a set of dimensions . and are objects that take a shape among a set of shapes. Each shape is defined as a finite set of shifted boxes, where each shifted box is described by a box in a -dimensional space at a given offset (from the origin of the shape) with given sizes. More precisely, a shifted box is an entity defined by its shape id , shift offset , and sizes . Then, a shape is defined as the union of shifted boxes sharing the same shape id. An object is an entity defined by its unique object identifier , shape id and origin .
An object does not overlap an object with respect to the set of dimensions if and only if for all shifted box associated with and for all shifted box associated with there exists a dimension such that the start of in dimension is greater than or equal to the end of in dimension , or the start of in dimension is greater than or equal to the end of in dimension .
Parts (A), (B) and (C) of Figure 5.134.1 respectively represent the potential shapes associated with the three objects of the example. Part (D) shows the position of the three objects of the example, where the first, second and third objects were respectively assigned shapes 1, 5 and 8. The coordinates of the leftmost lowest corner of each object are stressed in bold. The constraint holds since the three objects do not overlap (i.e., see part (D) if Figure 5.134.1).
Figure 5.134.1. The three objects of the example
The constraint allows to model directly a large number of placement problems.
In the two -dimensional case, when rectangles heights are all equal to one and when rectangles starts in the first dimension are all fixed, the constraint can be rewritten as a constraint corresponding to a system of constraints derived from the maximum cliques of the corresponding interval graph.
A sweep-based filtering algorithm for this constraint is described in [BeldiceanuCarlssonPoderSadekTruchet07]. Unlike previous sweep filtering algorithms which move a line for finding a feasible position for the origin of an object, this algorithm performs a recursive traversal of the multidimensional placement space. It explores all points of the domain of the origin of the object under focus, one by one, in increasing lexicographic order, until a point is found that is not infeasible for any non -overlapping constraints. To make the search efficient, instead of moving each time to the successor point, the search is arranged so that it skips points that are known to be infeasible for some non -overlapping constraint.
Within the context of breaking symmetries six different ways of integrating within a chain of lexicographical ordering constraints like for enforcing a lexicographic ordering on the origin coordinates of identical objects, are described in [AgrenCarlssonBeldiceanuSbihiTruchetZampelli09].
- See also
generalisation: ( added to ).
specialisation: (when rectangles heights are all equal to 1 and rectangles starts in the first dimension are all fixed), ( replaced by ).
modelling: scheduling with machine choice, calendars and preemption, disjunction, assignment dimension, assigning and scheduling tasks that run in parallel, assignment to the same set of values, relaxation dimension.
puzzles: squared squares, packing almost squares, Partridge, pentomino, Shikaku, smallest square for packing consecutive dominoes, smallest square for packing rectangles with distinct sizes, smallest rectangle area, Conway packing problem.