| 51. |
- Beldiceanu, Nicolas
(författare)
-
Sweep as a Generic Pruning Technique
- 2000. - 1
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 52. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Sweep as a generic pruning technique applied to constraint relaxation
- 2001. - 1
-
Konferensbidrag (refereegranskat)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.
|
|
| 53. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Sweep as a Generic Pruning Technique Applied to the Non-Overlapping Rectangles Constraint
- 2001. - 1
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 54. |
- 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.
|
|
| 55. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Sweep Synchronization as a Global Propagation Mechanism
- 2003. - 1
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 56. |
- 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)
|
|
| 57. |
|
|
| 58. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Using finite transducers for describing and synthesising structural time-series constraints
- 2015. - 5
-
Ingår i: Constraints. - : Springer. - 1383-7133 .- 1572-9354. ; 21:1, s. 22-40
-
Tidskriftsartikel (refereegranskat)abstract
- We describe a large family of constraints for structural time series by means of function composition. These constraints are on aggregations of features of patterns that occur in a time series, such as the number of its peaks, or the range of its steepest ascent. The patterns and features are usually linked to physical properties of the time series generator, which are important to capture in a constraint model of the system, i.e. a conjunction of constraints that produces similar time series. We formalise the patterns using finite transducers, whose output alphabet corresponds to semantic values that precisely describe the steps for identifying the occurrences of a pattern. Based on that description, we automatically synthesise automata with accumulators, as well as constraint checkers. The description scheme not only unifies the structure of the existing 30 time-series constraints in the Global Constraint Catalogue, but also leads to over 600 new constraints, with more than 100,000 lines of synthesised code.
|
|
| 59. |
- 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.
|
|
| 60. |
- Carlsson, Mats, et al.
(författare)
-
Arc-Consistency for a Chain of Lexicographic Ordering Constraints
- 2002. - 1
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 61. |
- Carlsson, Mats, et al.
(författare)
-
Dispensation order generation for pyrosequencing
- 2004. - 1
-
Ingår i: Proceedings. Bioinformatics 2004. Second Asia-Pacific Bioinformatics Conference (APBC2004). - 1920682112 ; , s. 327-332
-
Konferensbidrag (refereegranskat)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.
|
|
| 62. |
|
|
| 63. |
- Carlsson, Mats, et al.
(författare)
-
From constraints to finite automata to filtering algorithms
- 2004. - 1
-
Ingår i: Proceedings ESOP2004: Programming languages and systems. - Berlin, Heidelberg : Springer. - 9783540213130 ; , s. 94-108
-
Konferensbidrag (refereegranskat)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.
|
|
| 64. |
- Carlsson, Mats, et al.
(författare)
-
Multiplex dispensation order generation for pyrosequencing
- 2004. - 1
-
Konferensbidrag (refereegranskat)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.
|
|
| 65. |
- Carlsson, Mats, et al.
(författare)
-
Revisiting the Lexicographic Ordering Constraint
- 2002. - 1
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 66. |
- Letort, Arnaud, et al.
(författare)
-
A Scalable Sweep Algorithm for the Cumulative Constraint
- 2012. - 6
-
Konferensbidrag (refereegranskat)abstract
- This paper presents a sweep based algorithm for the cumulative constraint, which can operate in filtering mode as well as in greedy assignment mode. Given n tasks, this algorithm has a worst-case time complexity of O(n 2). In practice, we use a variant with better average-case complexity but worst-case complexity of O(n 2 log n), which goes down to O(n log n) when all tasks have unit duration, i.e. in the bin-packing case. Despite its worst-case time complexity, this algorithm scales well in practice, even when a significant number of tasks can be scheduled in parallel. It handles up to 1 million tasks in one single cumulative constraint in both Choco and SICStus.
|
|
| 67. |
- Letort, Arnaud, et al.
(författare)
-
A Synchronized Sweep Algorithm for the k-Dimensional Cumulative Constraint
- 2013. - 9
-
Ingår i: CPAIOR. - Berlin, Heidelberg : Springer. ; , s. 144-159
-
Konferensbidrag (refereegranskat)abstract
- This paper presents a sweep based algorithm for the k-dimensional Cumulative constraint, which can operate in filtering mode as well as in greedy assignment mode. Given n tasks and k resources, this algorithm has a worst-case time complexity of O(kn^2) but scales well in practice. In greedy assignment mode, it handles up to 1 million tasks with 64 resources in one single constraint in SICStus. In filtering mode, on our benchmarks, it yields a speed-up of about k^(3/4) when compared to its decomposition into k independent Cumulative constraints.
|
|
| 68. |
- Letort, Arnaud, et al.
(författare)
-
Synchronized sweep algorithms for scalable scheduling constraints
- 2013. - 7
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- This report introduces a family of synchronized sweep based filtering algorithms for handling scheduling problems involving resource and precedence constraints. The key idea is to filter all constraints of a scheduling problem in a synchronized way in order to scale better. In addition to normal filtering mode, the algorithms can run in greedy mode, in which case they perform a greedy assignment of start and end times. The filtering mode achieves a significant speed-up over the decomposition into independent cumulative and precedence constraints, while the greedy mode can handle up to 1 million tasks with 64 resources constraints and 2 million precedences. These algorithms were implemented in both CHOCO and SICStus.
|
|
| 69. |
- Letort, Arnaud, et al.
(författare)
-
Synchronized sweep algorithms for scalable scheduling constraints
- 2015. - 4
-
Ingår i: Constraints. - : Springer. - 1383-7133 .- 1572-9354. ; 19, s. 183-234
-
Tidskriftsartikel (refereegranskat)abstract
- This paper introduces a family of synchronized sweep-based filtering algorithms for handling scheduling problems involving resource and precedence constraints. The key idea is to filter all constraints of a scheduling problem in a synchronized way in order to scale better. In addition to normal filtering mode, the algorithms can run in greedy mode, in which case they perform a greedy assignment of start and end times. The filtering mode achieves a significant speed-up over the decomposition into independent CUMULATIVE and precedence constraints, while the greedy mode can handle up to 1 million tasks with 64 resource constraints and 2 million precedences. These algorithms were implemented in both CHOCO and SICStus.
|
|
| 70. |
|
|
| 71. |
|
|
| 72. |
- Razakarison, Naina, et al.
(författare)
-
GAC for a Linear Inequality and an Atleast Constraint with an Application to Learning Simple Polynomials
- 2013. - 6
-
Ingår i: Proceedings of the 6th Annual Symposium on Combinatorial Search, SoCS 2013. ; , s. 149-157
-
Konferensbidrag (refereegranskat)abstract
- We provide a filtering algorithm achieving GAC for the conjunction of constraints AtLeast(b,[x[0],x[1],...,x[n-1]],V) /\ Sum(i in 0..n-1)(a[i] c[i]) <= c where the AtLeast constraint enforces at least b variables out of x[0], x[1], ..., x[n-1] to be assigned a value in the set V. This work was motivated by learning simple polynomials, i.e. finding the coefficients of polynomials in several variables from example parameter and function values. We additionally require that coefficients be integers, and that most coefficients be assigned to zero or integers close to 0. These problems occur in the context of learning constraint models from sample solutions of different sizes. Experiments with this more global filtering show an improvement by several orders of magnitude compared to handling the constraints in isolation or with CostGCC, while also out-performing a 0/1 MIP model of the problem.
|
|
| 73. |
|
|
| 74. |
- Å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.
|
|
| 75. |
- Å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.
|
|
| 76. |
- Ågren, Magnus, et al.
(författare)
-
Tracing and explaining execution of CLP(FD) programs
- 2002. - 1
-
Ingår i: Proceedings of the 12th International Workshop on Logic Programming Environments, WLPE 2002.
-
Konferensbidrag (refereegranskat)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.
|
|
