| 1. |
- Aggoun, Abderrahmane, et al.
(författare)
-
Integrating rule-based modelling and constraint programming for solving industrial packing problems
- 2010. - 4
-
Ingår i: ERCIM News. - : ERCIM EEIG. - 0926-4981 .- 1564-0094. ; , s. 34-35
-
Tidskriftsartikel (populärvet., debatt m.m.)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. |
|
|
| 3. |
- Arafailova, Ekaterina, et al.
(författare)
-
Global Constraint Catalog Volume II: Time-Series Constraints
- 2016
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- First this report presents a restricted set of finite transducers used to synthesise structural time-series constraints described by means of a multi-layered function composition scheme. Second it provides the corresponding synthesised catalogue of structural time-series constraints where each constraint is explicitly described in terms of automata with accumulators.
|
|
| 4. |
- Arafailova, Ekaterina, et al.
(författare)
-
Systematic Derivation of Bounds and Glue Constraints for Time-Series Constraints
- 2016
-
Ingår i: Principles and Practice of Constraint Programming. - Cham : Springer Publishing Company. - 9783319449524 - 9783319449531 ; , s. 13-29
-
Konferensbidrag (refereegranskat)abstract
- Integer time series are often subject to constraints on the aggregation of the integer features of all occurrences of some pattern within the series. For example, the number of inflexions may be constrained, or the sum of the peak maxima, or the minimum of the peak widths. It is currently unknown how to maintain domain consistency efficiently on such constraints. We propose parametric ways of systematically deriving glue constraints, which are a particular kind of implied constraints, as well as aggregation bounds that can be added to the decomposition of time-series constraints [5]. We evaluate the beneficial propagation impact of the derived implied constraints and bounds, both alone and together.
|
|
| 5. |
|
|
| 6. |
- 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.
|
|
| 7. |
- Beldiceanu, Nicolas, et al.
(författare)
-
A Modelling Pearl with Sortedness Constraints
- 2015. - 9
-
Ingår i: GCAI 2015. Global Conference on Artificial Intelligence. - : EasyChair. ; , s. 27-41
-
Konferensbidrag (refereegranskat)abstract
- Some constraint programming solvers and constraint modelling languages feature the Sort(L,P,S) constraint, which holds if S is a nondecreasing rearrangement of the list L, the permutation being made explicit by the optional list P. However, such sortedness constraints do not seem to be used much in practice. We argue that reasons for this neglect are that it is impossible to require the underlying sort to be stable, so that Sort cannot be guaranteed to be a total-function constraint, and that L cannot contain tuples of variables, some of which form the key for the sort. To overcome these limitations, we introduce the StableKeysort constraint, decompose it using existing constraints, and propose a propagator. This new constraint enables a powerful modelling idiom, which we illustrate by elegant and scalable models of two problems that are otherwise hard to encode as constraint programs.
|
|
| 8. |
|
|
| 9. |
- Beldiceanu, Nicolas, et al.
(författare)
-
A New multi-resource cumulatives constraint with negative heights
- 2002. - 1
-
Ingår i: CP'2002, Principles and Practice of Constraint Programming. - Berlin, Heidelberg : Springer-Verlag. ; , s. 63-79
-
Konferensbidrag (refereegranskat)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.
|
|
| 10. |
- Beldiceanu, Nicolas, et al.
(författare)
-
A New Multi-Resource cumulatives Constraint with Negative Heights
- 2001. - 1
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 11. |
- Beldiceanu, Nicolas, et al.
(författare)
-
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
-
Konferensbidrag (refereegranskat)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.
|
|
| 12. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Assistant: Learning and robust decision support system for agile manufacturing environments
- 2021
-
Ingår i: IFAC-PapersOnLine. - : Elsevier. ; , s. 641-646
-
Konferensbidrag (refereegranskat)abstract
- The European project ASSISTANT will provide a set of AI-based digital twins that helps process engineers and production planners to operate collaborative mixed-model assembly lines based on the data collected from IoT devices and external data sources. Such a tool will help planners to design the assembly line, plan the production, operate the line, and improve process tuning. In addition, the system monitors the line in real-time, ensures that all required resources are available, and allows fast re-planning when necessary. ASSISTANT aims to make cost-effective decisions while ensuring product quality, safety and wellbeing of the workers, and managing the various sources of uncertainties. The resulting digital twin systems will be data-driven, agile, autonomous, collaborative and explainable, safe but reactive.
|
|
| 13. |
|
|
| 14. |
|
|
| 15. |
- 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.
|
|
| 16. |
- 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.
|
|
| 17. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Constructive Cardinality
- 2001. - 1
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 18. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Cost-Filtering Algorithms for the two Sides of the Sum of Weights of Distinct Values Constraint
- 2002. - 1
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 19. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Deriving Filtering Algorithms from Constraint Checkers
- 2004. - 1
-
Ingår i: Proceedings of Principles and Practice of Constraint Programming – CP 2004, 10th International Conference. - Berlin, Heidelberg : Swedish Institute of Computer Science. - 9783540232414 ; , s. 107-122
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 20. |
- Beldiceanu, Nicolas
(författare)
-
Generic filtering algorithms for generic global constraints
- 2003. - 1
-
Konferensbidrag (refereegranskat)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.
|
|
| 21. |
- 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.
|
|
| 22. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Global Constraint Catalog, 2nd Edition
- 2010. - 7
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 23. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Global Constraint Catalog, 2nd Edition (revision a)
- 2012. - 6
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 24. |
- 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.
|
|
| 25. |
|
|
| 26. |
- Beldiceanu, Nicolas
(författare)
-
Global constraints as graph properties on structured network of elementary constraints of the same type
- 2000. - 1
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 27. |
- 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.
|
|
| 28. |
|
|
| 29. |
- 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.
|
|
| 30. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Linking Prefixes and Suffixes for Constraints Encoded Using Automata with Accumulators
- 2014. - 7
-
Ingår i: Principles and Practice of Constraint Programming. - Cham : Springer International Publishing. - 9783319104270 ; , s. 142-157
-
Konferensbidrag (refereegranskat)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.
|
|
| 31. |
- 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.
|
|
| 32. |
- Beldiceanu, Nicolas, et al.
(författare)
-
New Filtering for the Cumulative Constraint in the Context of Non-Overlapping Rectangles
- 2011. - 5
-
Ingår i: Annals of Operations Research. - : Springer-Verlag. - 0254-5330 .- 1572-9338. ; 1, s. 27-50
-
Tidskriftsartikel (refereegranskat)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.
|
|
| 33. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Non-overlapping Constraints between Convex Polytopes
- 2001. - 1
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 34. |
- Beldiceanu, Nicolas, et al.
(författare)
-
On matrices, automata, and double counting
- 2010
-
Ingår i: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. - Berlin : Springer-Verlag. ; , s. 10-24
-
Konferensbidrag (refereegranskat)
|
|
| 35. |
|
|
| 36. |
- Beldiceanu, Nicolas, et al.
(författare)
-
On the Reification of Global Constraints
- 2012. - 8
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 37. |
- Beldiceanu, Nicolas, et al.
(författare)
-
On the reification of global constraints
- 2013
-
Ingår i: Constraints. - : Springer Science and Business Media LLC. - 1383-7133 .- 1572-9354. ; 18:1, s. 1-6
-
Tidskriftsartikel (refereegranskat)
|
|
| 38. |
- Beldiceanu, Nicolas, et al.
(författare)
-
On the Reification of Global Constraints (Abstract)
- 2015
-
Ingår i: Principles and practice of constraint programming, CP 2015. - : SPRINGER-VERLAG BERLIN. - 9783319232195 - 9783319232188 ; , s. 733-733
-
Konferensbidrag (refereegranskat)
|
|
| 39. |
|
|
| 40. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Propagating regular counting constraints
- 2014
-
Ingår i: Proc. 28th AAAI Conference on Artificial Intelligence. - Palo Alto, CA : AAAI Press. - 9781577356806 ; , s. 2616-2622
-
Konferensbidrag (refereegranskat)
|
|
| 41. |
- Beldiceanu, Nicolas
(författare)
-
Pruning for the cardinality-path constraint family
- 2001. - 1
-
Konferensbidrag (refereegranskat)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.
|
|
| 42. |
- Beldiceanu, Nicolas
(författare)
-
Pruning for the cardinality-path Constraint Family
- 2000. - 1
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 43. |
- Beldiceanu, Nicolas
(författare)
-
Pruning for the minimum constraint family and for the number of distinct values constraint family
- 2001. - 1
-
Konferensbidrag (refereegranskat)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.
|
|
| 44. |
- Beldiceanu, Nicolas
(författare)
-
Pruning for the minimum constraint family and for the number of distinct values constraint family
- 2001. - 1
-
Konferensbidrag (refereegranskat)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.
|
|
| 45. |
- Beldiceanu, Nicolas
(författare)
-
Pruning for the minimum Constraint Family and for the Number of Distinct Values Constraint Family
- 2000. - 1
-
Rapport (övrigt vetenskapligt/konstnärligt)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.
|
|
| 46. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Range-consistent forbidden regions of Allen's relations
- 2016. - 10
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- For all 8192 combinations of Allen's 13 relations between one task with origin oi and fixed length li and another task with origin oj and fixed length lj, we give a formula F(min(oj), max(oj), li, lj), where min(oj) and max(oj) respectively denote the earliest and the latest origin of task j, evaluating to a set of integers which are infeasible for oi for the given combination. Such forbidden regions are useful e.g. in a range-consistency maintaining propagator for an Allen constraint in finite domain constraint programming.
|
|
| 47. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Range-consistent forbidden regions of allen’s relations
- 2017
-
Konferensbidrag (refereegranskat)abstract
- For all 8192 combinations of Allen’s 13 relations between one task with origin oi and fixed length ℓi and another task with origin oj and fixed length ℓj, this paper shows how to systematically derive a formula F (oj, oj, ℓi, ℓj), where oj and oj respectively denote the earliest and the latest origin of task j, evaluating to a set of integers which are infeasible for oi for the given combination. Such forbidden regions allow maintaining range-consistency for an Allen constraint.
|
|
| 48. |
- 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.
|
|
| 49. |
- Beldiceanu, Nicolas, et al.
(författare)
-
Revisiting the cardinality operator and introducing the cardinality-path constraint family
- 2001. - 1
-
Konferensbidrag (refereegranskat)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.
|
|
| 50. |
|
|
