| 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. |
|
|
| 3. |
|
|
| 4. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Combining Tree Partitioning, Precedence, Incomparability, and Degree Constraints, with an Application to Phylogenetic and Ordered-Path Problems
- 2006
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- The \emphtree and \emphpath constraints, for digraph partitioning by vertex disjoint trees and paths respectively, are unified within a single global constraint, including a uniform treatment of a variety of useful side constraints, such as precedence, incomparability, and degree constraints. The approach provides a sharp improvement over an existing \emphpath constraint, but can also efficiently handle tree problems, such as the phylogenetic supertree construction problem. The key point of the filtering is to take partially into account the strong interactions between the tree partitioning problem and all the side constraints.
|
|
| 5. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Compiling business rules in a geometric constraint over k-dimensional objects and shapes
- 2009. - 1
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- It is well known that real-life applications rarely admit a constraint model expressed purely in terms of a few global constraints. Usually, the global constraints capture a relaxed form of the problem, but needs additional side-constraints to capture the full problem. Handling such side-constraints inside the global constraints, as opposed to in conjunction with it, improves propagation. Historically, this has been done by extending the global constraints with a host of specific options, each connected to a specific filtering method. Being able to express and filter side-constraints in a more uniform and systematic way would seem a more elegant and manageable solution. This report presents such a mechanism for the global non-overlapping constraint "geost", which handles the location in space of k-dimensional objects. Side-constraints are expressed as rules written in a language based on arithmetic and first-order logic, which should hold among the objects. We explain in detail the way the rules are compiled into a form that is accessed by the constraint's sweep-based filtering algorithm. In a first step, the rules are rewritten to Quantifier-Free Presburger Arithmetic (QFPA) formulas. Secondly, such formulas are transformed to generators of k-dimensional forbidden sets. Thirdly, the generators are transformed to procedures answering queries about candidate coordinate points for a given object. Such queries are at the heart of the filtering algorithm. The business rules allow to express a great variety of packing and placement constraints, while admitting effective filtering of the domain variables of the k-dimensional object, without the need to use spatial data structures. The constraint was used to directly encode the packing knowledge of a major car manufacturer, and was evaluated on several benchmarks.
|
|
| 6. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Global Constraint Catalog
- 2005. - 1
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- This report presents a catalog of global constraints where each constraint is explicitly described in terms of graph properties and/or automata. When available, it also presents some typical usage as well as some pointers to existing filtering algorithms.
|
|
| 7. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Global Constraint Catalogue: Past, Present and Future
- 2007. - 1
-
Ingår i: Constraints. - : Springer Science and Business Media LLC. - 1383-7133 .- 1572-9354. ; 12:1, s. 21-62
-
Tidskriftsartikel (refereegranskat)abstract
- The catalogue of global constraints is reviewed, focusing on the graph-based description of global constraints. A number of possible enhancements are proposed as well as several research paths for the development of the area.
|
|
| 8. |
- 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.
|
|
| 9. |
|
|
| 10. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Graph Properties Based Filtering
- 2006. - 1
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- This report presents a generic filtering scheme, based on the graph description of global constraints. This description is defined by a network of binary constraints and a list of elementary graph properties: each solution of the global constraint corresponds to a subgraph of the initial network, retaining only the satisfied binary constraints, and which fulfills all the graph properties. The graph-based filtering identifies the arcs of the network that belong or not to the solution subgraphs. The objective is to build, besides a catalog of global constraints, also a list of systematic filtering rules based on a limited set of graph properties. We illustrate this principle on some common graph properties and provide computational experiments of the effective filtering on the "group" constraint.
|
|
| 11. |
- Beldiceanu, Nicolas, et al.
(författare)
-
New filtering for the cumulative constraint in the context of non-overlapping rectangles
- 2008. - 1
-
Ingår i: CPAIOR 2008. - Berlin, Heidelberg : Springer. ; , s. 21-35
-
Konferensbidrag (refereegranskat)abstract
- This paper describes new filtering methods for the cumulative constraint. The first method introduces bounds for the so called longest cumulative hole problem and shows how to use these bounds in the context of the non-overlapping constraint. The second method introduces balancing knapsack constraints which relate the total height of the tasks that end at a specific time-point with the total height of the tasks that start at the same time-point. Experiments on tight rectangle packing problems show that these methods drastically reduce both the time and the number of backtracks for finding all solutions as well as for finding the first solution. For example, we found without backtracking all solutions to 66 perfect square instances of order 23-25 and sizes ranging from 332 times 332 to 661 times 661.
|
|
| 12. |
|
|
| 13. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Reformulation of global constraints based on constraint checkers
- 2005. - 1
-
Ingår i: Constraints. - : Springer Science and Business Media LLC. - 1383-7133 .- 1572-9354. ; 10
-
Tidskriftsartikel (refereegranskat)abstract
- This article deals with global constraints for which the set of solutions can be recognized by an extended finite automaton whose size is bounded by a polynomial in n, where n is the number of variables of the corresponding global constraint. By reducing the automaton to a conjunction of signature and transition constraints we show how to systematically obtain an automaton reformulation. Under some restrictions on the signature and transition constraints, this reformulation maintains arc-consistency. An implementation based on some constraints as well as on the metaprogramming facilities of SICStus Prolog is available. For a restricted class of automata we provide an automaton reformulation for the relaxed case, where the violation cost is the minimum number of variables to unassign in order to get back to a solution.
|
|
| 14. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Sweep synchronisation as a global propagation mechanism
- 2006. - 1
-
Ingår i: Computers & Operations Research. ; 3, s. 2835-2851
-
Tidskriftsartikel (refereegranskat)abstract
- This paper presents a new generic filtering algorithm that simultaneously considers n conjunctions of constraints as well as those constraints mentioning some variables Y_k of the pairs (X,Y_k) (1 <= k <= n) occurring in these conjunctions. The main benefit of this new technique comes from the fact that, for adjusting the bounds of a variable X according to n conjunctions, we do not perform n sweeps in an independent way but rather synchronize them. We then specialize this technique to the non-overlapping rectangles constraint where we consider the case where several rectangles of height one have the same X coordinate for their origin as well as the same length. For this specific constraint we come up with an incremental bipartite matching algorithm which is triggered while we sweep over the time axis. We illustrate the usefulness of this new pruning method on a timetabling problem, where each task can’t be interrupted and requires the simultaneous availability of n distinct persons. Each person has his own periods of unavailability and can only perform one task at a time.
|
|
| 15. |
- Beldiceanu, Nicolas, et al.
(författare)
-
The tree constraint
- 2005
-
Ingår i: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: Second International Conference, CPAIOR 2005, Proceedings. - 3540261524 ; , s. 64-78
-
Konferensbidrag (refereegranskat)
|
|
| 16. |
- Carlsson, Mats, et al.
(författare)
-
A geometric constraint over k-dimensional objects and shapes subject to business rules
- 2008. - 1
-
Ingår i: Proc. CP'2008. - Berlin, Heidelberg : Swedish Institute of Computer Science. ; , s. 220-234
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- This report presents a global constraint that enforces rules written in a language based on arithmetic and first-order logic to hold among a set of objects. In a first step, the rules are rewritten to Quantifier-Free Presburger Arithmetic (QFPA) formulas. Secondly, such formulas are compiled to generators of k-dimensional forbidden sets. Such generators are a generalization of the indexicals of cc(FD). Finally, the forbidden sets generated by such indexicals are aggregated by a sweep-based algorithm and used for filtering. The business rules allow to express a great variety of packing and placement constraints, while admitting efficient and effective filtering of the domain variables of the k-dimensional object, without the need to use spatial data structures. The constraint was used to directly encode the packing knowledge of a major car manufacturer and tested on a set of real packing problems under these rules, as well as on a packing-unpacking problem.
|
|
| 17. |
|
|
| 18. |
- Å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.
|
|
| 19. |
- Å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.
|
|
