| 1. |
- Beldiceanu, Nicolas, et al.
(author)
-
A New multi-resource cumulatives constraint with negative heights
- 2002. - 1
-
In: CP'2002, Principles and Practice of Constraint Programming. - Berlin, Heidelberg : Springer-Verlag. ; , s. 63-79
-
Conference paper (peer-reviewed)abstract
- This paper presents a new cumulatives constraint which generalizes the original cumulative constraint in different ways. The two most important aspects consist in permitting multiple cumulative resources as well as negative heights for the resource consumption of the tasks. This allows modeling in an easy way new scheduling and planning problems. The introduction of negative heights has forced us to come up with new propagation algorithms and to revisit existing ones. The first propagation algorithm is derived from an idea called sweep which is extensively used in computational geometry; the second algorithm is based on a combination of sweep and constructive disjunction, while the last is a generalization of task intervals to this new context. A real-life timetabling problem originally motivated this constraint which was implemented within the SICStus finite domain solver and evaluated against different problem patterns.
|
|
| 2. |
- Beldiceanu, Nicolas, et al.
(author)
-
A New Multi-Resource cumulatives Constraint with Negative Heights
- 2001. - 1
-
Reports (other academic/artistic)abstract
- This paper presents a new cumulatives constraint which generalizes the original cumulative constraint in different ways. The two most important aspects consist in permitting multiple cumulative resources as well as negative heights for the resource consumption of the tasks. This allows modeling in an easy way new scheduling and planning problems. The introduction of negative heights has forced us to come up with new propagation algorithms and to revisit existing ones. The first propagation algorithm is derived from an idea called sweep which is extensively used in computational geometry; the second algorithm is based on a combination of sweep and constructive disjunction, while the last is a generalization of task intervals to this new context. A real-life timetabling problem originally motivated this constraint which was implemented within the SICStus finite domain solver and evaluated against different problem patterns.
|
|
| 3. |
- Beldiceanu, Nicolas, et al.
(author)
-
Constructive Cardinality
- 2001. - 1
-
Reports (other academic/artistic)abstract
- We describe a set of necessary conditions that are useful for generating propagation algorithms for the cardinality operator as well as for over-constrained problems with preferences. Constructive disjunction as well as the entailments rules originally proposed for the cardinality operator can be seen as simple cases of these necessary conditions. In addition these necessary conditions have the advantage of providing more pruning.
|
|
| 4. |
- Beldiceanu, Nicolas, et al.
(author)
-
Cost-Filtering Algorithms for the two Sides of the Sum of Weights of Distinct Values Constraint
- 2002. - 1
-
Reports (other academic/artistic)abstract
- This article introduces the sum of weights of distinct values constraint, which can be seen as a generalization of the number of distinct values as well as of the alldifferent, and the relaxed alldifferent constraints. This constraint holds if a cost variable is equal to the sum of the weights associated to the distinct values taken by a given set of variables. For the first aspect, which is related to domination, we present four filtering algorithms. Two of them lead to perfect pruning when each domain variable consists of one set of consecutive values, while the two others take advantage of holes in the domains. For the second aspect, which is connected to maximum matching in a bipartite graph, we provide a complete filtering algorithm for the general case. Finally we introduce several generic deduction rules, which link both aspects of the constraint. These rules can be applied to other optimization constraints such as the minimum weight alldifferent constraint or the global cardinality constraint with costs. They also allow taking into account external constraints for getting enhanced bounds for the cost variable. In practice, the sum of weights of distinct values constraint occurs in assignment problems where using a resource once or several times costs the same. It also captures domination problems where one has to select a set of vertices in order to control every vertex of a graph.
|
|
| 5. |
- Beldiceanu, Nicolas, et al.
(author)
-
Deriving Filtering Algorithms from Constraint Checkers
- 2004. - 1
-
In: Proceedings of Principles and Practice of Constraint Programming – CP 2004, 10th International Conference. - Berlin, Heidelberg : Swedish Institute of Computer Science. - 9783540232414 ; , s. 107-122
-
Reports (other academic/artistic)abstract
- This report 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 reformulating the automaton as a conjunction of signature and transition constraints we show how to systematically obtain a filtering algorithm. Under some restrictions on the signature and transition constraints this filtering algorithm achieves 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 a filtering algorithm for the relaxed case, where the violation cost is the minimum number of variables to unassign in order to get back to a solution.
|
|
| 6. |
- Beldiceanu, Nicolas
(author)
-
Generic filtering algorithms for generic global constraints
- 2003. - 1
-
Conference paper (peer-reviewed)abstract
- In a first phase, this talk presents an extension of the framework for classifying global constraints that was introduced in 2000. This is concretely illustrated by showing how constraints like alldifferent, cumulative, cutset, cycle, diffn, element, global cardinality, lexicographic ordering, soft alldifferent, or stretch fit into this framework. In a second phase, this talk motivates the need for generic filtering algorithms from different viewpoints. Finally it gives some preliminary hints of how such generic algorithms could be developed.
|
|
| 7. |
|
|
| 8. |
- Beldiceanu, Nicolas
(author)
-
Global constraints as graph properties on structured network of elementary constraints of the same type
- 2000. - 1
-
Reports (other academic/artistic)abstract
- This report introduces a classification scheme for the global constraints. This classification is based on four basic ingredients from which one can generate almost all existing global constraints and come up with new interesting constraints. Global constraints are defined in a very concise way, in term of graph properties that have to hold, where the graph is a structured network of same elementary constraints. Since this classification is based on the internal structure of the global constraints it is also a strong hint for the pruning algorithms of the global constraints.
|
|
| 9. |
- Beldiceanu, Nicolas, et al.
(author)
-
Non-overlapping Constraints between Convex Polytopes
- 2001. - 1
-
Reports (other academic/artistic)abstract
- This paper deals with non-overlapping constraints between convex polytopes. Non-overlapping detection between fixed objects is a fundamental geometric primitive that arises in many applications. However from a constraint perspective it is natural to extend the previous problem to a non-overlapping constraint between two objects for which both positions are not yet fixed. A first contribution is to present theorems for convex polytopes which allow coming up with general necessary conditions for non-overlapping. These theorems can be seen as a generalization of the notion of compulsory part which was introduced in 1984 by Lahrichi and Gondran [6] for managing non-overlapping constraint between rectangles. Finally, a second contribution is to derive from the previous theorems efficient filtering algorithms for two special cases: the non-overlapping constraint between two convex polygons as well as the non-overlapping constraint between d-dimensional boxes.
|
|
| 10. |
- Beldiceanu, Nicolas
(author)
-
Pruning for the cardinality-path constraint family
- 2001. - 1
-
Conference paper (peer-reviewed)abstract
- This paper presents generic propagation algorithms for the cardinality-path constraint family. This is a restricted form of the cardinality operator that allows stating constraints on sliding sequences of consecutive variables. Taking advantage of these restrictions permits coming up with more efficient algorithms. Moreover the paper shows how to extend these propagation algorithms in order to partially integrate external constraints that have to hold. From an application point of view the cardinality-path constraint allows to express a huge variety of regulation constraints occurring in personnel planning problems.
|
|
| 11. |
- Beldiceanu, Nicolas
(author)
-
Pruning for the cardinality-path Constraint Family
- 2000. - 1
-
Reports (other academic/artistic)abstract
- This paper presents generic propagation algorithms for the cardinality-path constraint family. This is a restricted form of the cardinality operator that allows stating constraints on sliding sequences of consecutive variables. Taking advantage of these restrictions permits coming up with more efficient algorithms. Moreover the paper shows how to extend these propagation algorithms in order to partially integrate external constraints that have to hold. From an application point of view the cardinality-path constraint allows to express a huge variety of regulation constraints occurring in personnel planning problems.
|
|
| 12. |
- Beldiceanu, Nicolas
(author)
-
Pruning for the minimum constraint family and for the number of distinct values constraint family
- 2001. - 1
-
Conference paper (peer-reviewed)abstract
- The paper presents propagation rules that are common to the minimum constraint family and to the number of distinct values constraint family. One practical interest of the paper is to describe an implementation of the number of distinct values constraint. This is a quite common counting constraint that one encounters in many practical applications such as time tabling or frequency allocation problems. A second important contribution is to provide a pruning algorithm for the constraint "at most n distinct values for a set of variables". This can be considered as the counterpart of Regin's algorithm for the all different constraint where one enforces having at least n distinct values for a given set of n variables.
|
|
| 13. |
- Beldiceanu, Nicolas
(author)
-
Pruning for the minimum constraint family and for the number of distinct values constraint family
- 2001. - 1
-
Conference paper (peer-reviewed)abstract
- The paper presents propagation rules that are common to the minimum constraint family and to the number of distinct values constraint family. One practical interest of the paper is to describe an implementation of the number of distinct values constraint. This is a quite common counting constraint that one encounters in many practical applications such as time tabling or frequency allocation problems.
|
|
| 14. |
- Beldiceanu, Nicolas
(author)
-
Pruning for the minimum Constraint Family and for the Number of Distinct Values Constraint Family
- 2000. - 1
-
Reports (other academic/artistic)abstract
- The paper presents propagation rules that are common to the minimum constraint family and to the number of distinct values constraint family. One original contribution is to provide a geometrical interpretation of these rules that can be used by a generic sweep pruning algorithm. Finally one practical interest of the paper is to describe an implementation of the number of distinct values constraint. This is a quite common counting constraint that one encounters in many practical applications such as timetabling or frequency allocation problems.
|
|
| 15. |
- Beldiceanu, Nicolas, et al.
(author)
-
Revisiting the cardinality operator and introducing the cardinality-path constraint family
- 2001. - 1
-
Conference paper (peer-reviewed)abstract
- This paper presents generic propagation algorithms for the cardinality-path constraint family. This is a restricted form of the cardinality operator that allows stating constraints on sliding sequences of consecutive variables. Taking advantage of these restrictions permits coming up with more efficient algorithms. Moreover the paper shows how to extend these propagation algorithms in order to partially integrate external constraints that have to hold. From an application point of view the cardinality-path constraint allows to express a huge variety of regulation constraints occurring in personnel planning problems.
|
|
| 16. |
|
|
| 17. |
- Beldiceanu, Nicolas
(author)
-
Sweep as a Generic Pruning Technique
- 2000. - 1
-
Reports (other academic/artistic)abstract
- This report presents a generic pruning technique that aggregates several constraints sharing some variables. The method is derived from an idea called sweep that is extensively used in computational geometry. A first benefit of this technique comes from the fact that it can be applied on several families of global constraints. A second main advantage is that it does not lead to any memory consumption problem since it only requires temporary memory that can be reclaimed after each invocation of the method. This technique has been used inside the SICStus finite domain solver in order to implement several global constraints.
|
|
| 18. |
- Beldiceanu, Nicolas, et al.
(author)
-
Sweep as a generic pruning technique applied to constraint relaxation
- 2001. - 1
-
Conference paper (peer-reviewed)abstract
- We introduce a new generic filtering algorithm for handling constraint relaxation within constraint programming. More precisely, we first present a generic pruning technique, which is useful for a special case of the cardinality operator where all the constraints have at least two variables in common. This method is based on a generalisation of a sweep algorithm, which handles a conjunction of constraints to the case where one just knows the minimum and maximum number of constraints that have to hold. The main benefit of this new technique comes from the fact that, even if we don't know which, and exactly how many constraints, will hold in the final solution, we can still prune the variables of those constraints right from the beginning according to the minimum and maximum number of constraints that have to hold. We then show how to extend the previous sweep algorithm in order to handle preferences among constraints. Finally, we specialise this technique to an extension of the non-overlapping rectangles constraint, where we permit controlling how many non-overlapping constraints should hold. This allows handling over-constrained placement problems and provides constraint propagation even if some non-overlapping constraints have to be relaxed.
|
|
| 19. |
- Beldiceanu, Nicolas, et al.
(author)
-
Sweep as a Generic Pruning Technique Applied to the Non-Overlapping Rectangles Constraint
- 2001. - 1
-
Reports (other academic/artistic)abstract
- We first present a generic pruning technique which aggregates several constraints sharing some variables. The method is derived from an idea called \dfn{sweep} which is extensively used in computational geometry. A first benefit of this technique comes from the fact that it can be applied on several families of global constraints. A second main advantage is that it does not lead to any memory consumption problem since it only requires temporary memory that can be reclaimed after each invocation of the method. We then specialize this technique to the non-overlapping rectangles constraint, describe several optimizations, and give an empirical evaluation based on six sets of test instances of different pattern.
|
|
| 20. |
- Beldiceanu, Nicolas, et al.
(author)
-
Sweep Synchronization as a Global Propagation Mechanism
- 2003. - 1
-
Reports (other academic/artistic)abstract
- This paper presents a new generic filtering algorithm that simultaneously considers n conjunctions of constraints as well as those constraints mentioning some variables Yk of the pairs X,Yk (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 specializes 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 its own periods of unavailability and can only perform one task at a time.
|
|
| 21. |
- Carlsson, Mats, et al.
(author)
-
Arc-Consistency for a Chain of Lexicographic Ordering Constraints
- 2002. - 1
-
Reports (other academic/artistic)abstract
- We present an arc-consistency algorithm for a chain of lexicographic ordering constraints on $m$ vectors of $n$ variables each. The algorithm maintains arc-consistency and runs in $O(nmd)$ time per invocation, where $d$ is the cost of certain domain operations.
|
|
| 22. |
- Carlsson, Mats, et al.
(author)
-
Dispensation order generation for pyrosequencing
- 2004. - 1
-
In: Proceedings. Bioinformatics 2004. Second Asia-Pacific Bioinformatics Conference (APBC2004). - 1920682112 ; , s. 327-332
-
Conference paper (peer-reviewed)abstract
- This article describes a dispensation order generation algorithm for genotyping using the Pyrosequencing method. The input template of the algorithm is a slightly restricted regular expression over the DNA strings that can be expected in a given sample. The algorithm computes a dispensation order that allows for determining, for each polymorphism in the input template, the genotype of any sample. The algorithm has the structure of a non-deterministic rewrite system, which gives rise to a search tree. We show that within any branch of the search tree, the rewrite system is confluent and terminating. We use nogood generation and limited discrepancy search to prune the search tree and to focus the search for shorter dispensation orders before looking for longer ones. The algorithm as described herein assumes samples from a diploid genome, but can readily be generalized to general k-ploid genomes.
|
|
| 23. |
- Carlsson, Mats, et al.
(author)
-
From constraints to finite automata to filtering algorithms
- 2004. - 1
-
In: Proceedings ESOP2004: Programming languages and systems. - Berlin, Heidelberg : Springer. - 9783540213130 ; , s. 94-108
-
Conference paper (peer-reviewed)abstract
- We introduce an approach to designing filtering algorithms by derivation from finite automata operating on constraint signatures. We illustrate this approach in two case studies of constraints on vectors of variables. This has enabled us to derive an incremental filtering algorithm that runs in O(n) plus amortized O(1) time per propagation event for the lexicographic ordering constraint over two vectors of size n, and an O(nmd) time filtering algorithm for a chain of m-1 such constraints, where d is the cost of certain domain operations. Both algorithms maintain hyperarc consistency. Our approach can be seen as a first step towards a methodology for semi-automatic development of filtering algorithms.
|
|
| 24. |
- Carlsson, Mats, et al.
(author)
-
Multiplex dispensation order generation for pyrosequencing
- 2004. - 1
-
Conference paper (peer-reviewed)abstract
- This paper introduces the multiplex dispensation order generation problem, a real-life combinatorial problem that arises in the context of analyzing large numbers of short to medium length DNA sequences. The problem is modeled as a constraint optimization problem (COP). We present the COP, its constraint programming formulation, and a custom search procedure. We give some experimental data supporting our design decisions. One of the lessons learnt from this study is that the ease with which the relevant constraints are expressed can be a crucial factor in making design decisions in the COP model.
|
|
| 25. |
- Carlsson, Mats, et al.
(author)
-
Revisiting the Lexicographic Ordering Constraint
- 2002. - 1
-
Reports (other academic/artistic)abstract
- We present a global consistency algorithm for the lexicographic ordering constraint on two vectors of $n$ variables. The algorithm maintains arc-consistency, runs in $O(n)$ time on posting plus amortized $O(1)$ time per propagation event, and detects entailment or rewrites itself to a simpler constraint whenever possible. The algorithm was derived from a finite automaton operating on a string which captures the relationship between each variable pair of the two vectors.
|
|
| 26. |
|
|
| 27. |
- Ågren, Magnus, et al.
(author)
-
Tracing and explaining execution of CLP(FD) programs
- 2002. - 1
-
In: Proceedings of the 12th International Workshop on Logic Programming Environments, WLPE 2002.
-
Conference paper (peer-reviewed)abstract
- Previous work in the area of tracing CLP(FD) programs mainly focuses on providing information about control of execution and domain modification. In this paper, we present a trace structure that provides information about additional important aspects. We incorporate explanations in the trace structure, i.e. reasons for why certain solver actions occur. Furthermore, we come up with a format for describing the execution of the filtering algorithms of global constraints. Some new ideas about the design of the trace are also presented. For example, we have modeled our trace as a nested block structure in order to achieve a hierarchical view. Also, new ways about how to represent and identify different entities such as constraints and domain variables are presented.
|
|
