| 1. |
- Aggoun, Abderrahmane, et al.
(author)
-
Integrating rule-based modelling and constraint programming for solving industrial packing problems
- 2010. - 4
-
In: ERCIM News. - : ERCIM EEIG. - 0926-4981 .- 1564-0094. ; , s. 34-35
-
Journal article (pop. science, debate, etc.)abstract
- Packing items in bins is an old but nevertheless challenging combinatorial problem with numerous applications in industry. We report on an original approach based on constraint programming and rule-based modelling, which has been investigated in the framework of the FP6 ‘specific targeted research project’ Net-WMS (Towards integrating virtual reality and optimization techniques in a new generation of Networked businesses in Warehouse Management Systems under constraints). It has applications in the automotive industry.
|
|
| 2. |
- Beldiceanu, Nicolas, et al.
(author)
-
An O(n log n) Bound Consistency Algorithm for the Conjunction of an alldifferent and an Inequality between a Sum of Variables and a Constant, and its Generalization
- 2012. - 13
-
Conference paper (peer-reviewed)abstract
- This paper gives an O(n log n) bound-consistency filtering algorithm for the conjunction alldifferent(V0,V1,…,Vn−1)∧ f(V0)⌖f(V1)⌖…⌖f(Vn−1) ≤ cst, (V0,V1,…,Vn−1,cst ∊ N+), where (N,⌖) is a commutative group, f is a unary function, and both ⌖ and f are monotone increasing. This complexity is equal to the complexity of the bound-consistency algorithm of the alldifferent constraint.
|
|
| 3. |
- Beldiceanu, Nicolas, et al.
(author)
-
Global Constraint Catalog, 2nd Edition
- 2010. - 7
-
Reports (other academic/artistic)abstract
- This report presents a catalogue of global constraints where each constraint is explicitly described in terms of graph properties and/or automata and/or first order logical formulae with arithmetic. When available, it also presents some typical usage as well as some pointers to existing filtering algorithms.
|
|
| 4. |
- Beldiceanu, Nicolas, et al.
(author)
-
Global Constraint Catalog, 2nd Edition (revision a)
- 2012. - 6
-
Reports (other academic/artistic)abstract
- This report presents a catalogue of global constraints where each constraint is explicitly described in terms of graph properties and/or automata and/or first order logical formulae with arithmetic. When available, it also presents some typical usage as well as some pointers to existing filtering algorithms.
|
|
| 5. |
- Beldiceanu, Nicolas, et al.
(author)
-
Linking Prefixes and Suffixes for Constraints Encoded Using Automata with Accumulators
- 2014. - 7
-
In: Principles and Practice of Constraint Programming. - Cham : Springer International Publishing. - 9783319104270 ; , s. 142-157
-
Conference paper (peer-reviewed)abstract
- Consider a constraint on a sequence of variables functionally determining a result variable that is unchanged under reversal of the sequence. Most such constraints have a compact encoding via an automaton augmented with accumulators, but it is unknown how to maintain domain consistency efficiently for most of them. Using such an automaton for such a constraint, we derive an implied constraint between the result variables for a sequence, a prefix thereof, and the corresponding suffix. We show the usefulness of this implied constraint in constraint solving, both by local search and by propagation-based systematic search.
|
|
| 6. |
- Beldiceanu, Nicolas, et al.
(author)
-
New Filtering for the Cumulative Constraint in the Context of Non-Overlapping Rectangles
- 2011. - 5
-
In: Annals of Operations Research. - : Springer-Verlag. - 0254-5330 .- 1572-9338. ; 1, s. 27-50
-
Journal article (peer-reviewed)abstract
- This article 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 65 perfect square instances of order 22-25 and sizes ranging from 192x192 to 661x661.
|
|
| 7. |
- Beldiceanu, Nicolas, et al.
(author)
-
On matrices, automata, and double counting
- 2010
-
In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. - Berlin : Springer-Verlag. ; , s. 10-24
-
Conference paper (peer-reviewed)
|
|
| 8. |
|
|
| 9. |
- Beldiceanu, Nicolas, et al.
(author)
-
On the Reification of Global Constraints
- 2012. - 8
-
Reports (other academic/artistic)abstract
- We introduce a simple idea for deriving reified global constraints in a systematic way. It is based on the observation that most global constraints can be reformulated as a conjunction of pure functional dependency constraints together with a constraint that can be easily reified. We first show how the core constraints of the Global Constraint Catalogue can be reified and we then identify several reification categories that apply to at least 82% of the constraints in the Global Constraint Catalogue.
|
|
| 10. |
- Beldiceanu, Nicolas, et al.
(author)
-
On the reification of global constraints
- 2013
-
In: Constraints. - : Springer Science and Business Media LLC. - 1383-7133 .- 1572-9354. ; 18:1, s. 1-6
-
Journal article (peer-reviewed)
|
|
| 11. |
- Beldiceanu, Nicolas, et al.
(author)
-
Propagating regular counting constraints
- 2014
-
In: Proc. 28th AAAI Conference on Artificial Intelligence. - Palo Alto, CA : AAAI Press. - 9781577356806 ; , s. 2616-2622
-
Conference paper (peer-reviewed)
|
|
| 12. |
|
|
| 13. |
- Letort, Arnaud, et al.
(author)
-
A Scalable Sweep Algorithm for the Cumulative Constraint
- 2012. - 6
-
Conference paper (peer-reviewed)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.
|
|
| 14. |
- Letort, Arnaud, et al.
(author)
-
A Synchronized Sweep Algorithm for the k-Dimensional Cumulative Constraint
- 2013. - 9
-
In: CPAIOR. - Berlin, Heidelberg : Springer. ; , s. 144-159
-
Conference paper (peer-reviewed)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.
|
|
| 15. |
- Letort, Arnaud, et al.
(author)
-
Synchronized sweep algorithms for scalable scheduling constraints
- 2013. - 7
-
Reports (other academic/artistic)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.
|
|
| 16. |
|
|
| 17. |
- Razakarison, Naina, et al.
(author)
-
GAC for a Linear Inequality and an Atleast Constraint with an Application to Learning Simple Polynomials
- 2013. - 6
-
In: Proceedings of the 6th Annual Symposium on Combinatorial Search, SoCS 2013. ; , s. 149-157
-
Conference paper (peer-reviewed)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.
|
|
