Multiset Ordering Constraints (2009)
Frisch, Alan M., Miguel, Ian, Kiziltan, Zeynep, Hnich, Brahim, Walsh, Toby
We identify a new and important global (or non-binary) constraint. This constraint ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. This constraint is...
Filtering Algorithms for the Multiset Ordering Constraint (2009)
Frisch, Alan, Hnich, Brahim, Kiziltan, Zeynep, Miguel, Ian, Walsh, Toby
Constraint programming (CP) has been used with great success to tackle a wide variety of constraint satisfaction problems which are computationally intractable in general. Global constraints are one...
The Parameterized Complexity of Global Constraints (2009)
Bessiere, Christian, Hebrard, Emmanuel, Hnich, Brahim, Kiziltan, Zeynep, Walsh, Toby
We argue that parameterized complexity is a useful tool with which to study global constraints. In particular, we show that many global constraints which are intractable to propagate completely have...
SLIDE: A Useful Special Case of the CARDPATH Constraint (2009)
Bessiere, Christian, Hebrard, Emmanuel, Hnich, Brahim, Kiziltan, Zeynep, Walsh, Toby
We study the CardPath constraint. This ensures a given constraint holds a number of times down a sequence of variables. We show that SLIDE, a special case of CardPath where the slid constraint must...
Bessiere, Christian, Hebrard, Emmanuel, Hnich, Brahim, Kiziltan, Zeynep, Walsh, Toby
We propose Range and Roots which are two common patterns useful for specifying a wide range of counting and occurrence constraints. We design specialised propagation algorithms for these two...
The Range and Roots Constraints: Algorithms and Implementation (2008)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. We recently proposed a simple declarative language for specifying a wide range of counting and occurrence constraints. The language uses just two global primitives: the Range constraint,...
Breaking Row and Column Symmetryin Matrix Models (2008)
Pierre Flener, Alan M. Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel, Justin Pearson, ...
The Range and Roots Constraints: Algorithms and Implementation (2008)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. We recently proposed a simple declarative language for specifying a wide range of counting and occurrence constraints. The language uses just two global primitives: the Range constraint,...
CP-based Local Branching (2008)
Zeynep Kiziltan, Andrea Lodi, Michela Milano, Fabio Parisini
Abstract. We propose the integration and extension of the local branching search strategy in Constraint Programming (CP). Local branching is a general purpose heuristic method which searches locally...
Group-graphs associated with Row and Column Symmetries of Matrix Models: some observations (2008)
Zeynep Kiziltan, Michela Milano
Abstract. The effect of symmetry-breaking constraints is often evaluated empirically. In order to understand which symmetric configurations are removed by a set of constraints, we have to understand...
The Range and Roots Constraints: Algorithms and Implementation (2008)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. We recently proposed a simple declarative language for specifying a wide range of counting and occurrence constraints. The language uses just two global primitives: the Range constraint,...
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. A wide range of counting and occurrence constraints can be specified with just two global primitives: the Range constraint, which computes the range of values used by a sequence of...
Reformulating global constraints: the Slide and Regular constraints (2008)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Claude-guy Quimper, Toby Walsh, ...
Abstract. Global constraints are useful for modelling and reasoning about real-world combinatorial problems. Unfortunately, developing propagation algorithms to reason about global constraints...
Brahim Hnich, Zeynep Kiziltan, Toby Walsh
constraints by composition: lexicographic ordering with sums
Abstract. We propose extending constraint solvers with multiset variables. That is, variables whose values are multisets. Such an extension can help prevent introducing unnecessary symmetry into a...
Pierre Flener, Brahim Hnich, Zeynep Kiziltan
Abstract. In constraint solvers, variable and value ordering heuristics are used to finetune the performance of the underlying search and propagation algorithms. However, few guidelines have been...
Alan Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel, Toby Walsh
Abstract. We propose some global constraints for lexicographic orderings on vectors of variables. These constraints are very useful for breaking a certain kind of symmetry arising in matrices of...
Filtering algorithms for the NValue constraint (2006)
Bessiere, Christian, Hebrard, Emmanuel, Hnich, Brahim, Kiziltan, Zeynep, Walsh, Toby
none
The Range Constraint: Algorithms and Implementation (2006)
Bessiere, Christian, Hebrard, Emmanuel, Hnich, Brahim, Kiziltan, Zeynep, Walsh, Toby
N/A
Filtering algorithms for the NValue constraint (2006)
Bessiere, Christian, Hebrard, Emmanuel, Hnich, Brahim, Kiziltan, Zeynep, Walsh, Toby
none
The Range Constraint: Algorithms and Implementation (2006)
Bessiere, Christian, Hebrard, Emmanuel, Hnich, Brahim, Kiziltan, Zeynep, Walsh, Toby
N/A
Propagation algorithms for lexicographic ordering constraints (2006)
Alan M. Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel, Toby Walsh
Finite-domain constraint programming has been used with great success to tackle a wide variety of combinatorial problems in industry and academia. To apply finite-domain constraint programming to a...
The Range constraint: Algorithms and implementation (2006)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. We recently proposed a simple declarative language for specifying a wide range of counting and occurrence constraints. The language uses just two global primitives: the Range constraint,...
The SLIDE Meta-Constraint (2006)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
We study the SLIDE meta-constraint. This slides a constraint down one or more sequences of variables. We show that SLIDE can be used to encode and propagate a wide range of global constraints. We...
The Range Constraint: Algorithms and Implementation (2006)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
We recently proposed a simple declarative language for specifying a wide range of counting and occurrence constraints. The language uses just two global primitives: the Range constraint, which...
Among, common and disjoint constraints (2006)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. Among, Common and Disjoint are global constraints useful in modelling problems involving resources. We study a number of variations of these constraints over integer and set variables. We...
The Range constraint: Algorithms and implementation (2006)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. We recently proposed a simple declarative language for specifying a wide range of counting and occurrence constraints. The language uses just two global primitives: the Range constraint,...
The Range constraint: Algorithms and implementation (2006)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Range constraint based on aflow algorithm. We propose an extension of the Range constraint where we haveconstraints on the cardinality of the set variables. We also show that decomposing occurence...
Among, common and disjoint constraints (2006)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan
Abstract. Among, Common and Disjoint are global constraints useful in modelling problems involving resources. We study a number of variations of these constraints over integer and set variables. We...
Filtering algorithms for the NValue constraint (2005)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. The constraint NValue counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing...
Filtering algorithms for the NValue constraint (2005)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. The NValue constraint counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing...
Filtering algorithms for the NValue constraint (2005)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. The constraint NValue counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing...
Filtering algorithms for the NValue constraint (2005)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. The NValue constraint counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing...
Filtering algorithms for the NValue constraint (2005)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. The constraint NValue counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing...
Filtering Algorithms for the NValue Constraint (2005)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, And Toby Walsh, Toby Walsh
The constraint NValue counts the number of di#erent values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing even the...
Filtering algorithms for the NValue constraint (2005)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. The constraint NValue counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing...
Filtering algorithms for the NValue constraint (2005)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. The NValue constraint counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing...
Filtering algorithms for the NValue constraint (2005)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. The constraint NValue counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing...
Symmetry Breaking Ordering Constraints (2004)
Many problems in business, industry, and academia can be modelled as constraint programs consisting of matrices of decision variables. Such “matrix models” often have symmetry. In particular,...
Symmetry Breaking Ordering Constraints (2004)
Many problems in business, industry, and academia can be modelled as constraint programs consisting of matrices of decision variables. Such “matrix models” often have symmetry. In particular,...
Hybrid modelling for robust solving (2004)
Brahim Hnich, Zeynep Kiziltan, Ian Miguel, Toby Walsh
⋆ We would like to thank C. Castro and S. Manzano for providing us with the real-life instances they used in their experiments. The first and the last authors are supported by Science Foundation...
Combining symmetry breaking with other constraints: lexicographic ordering with sums (2004)
Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. We introduce a new global constraint which combines together the lexicographic ordering constraint with some sum constraints. Lexicographic ordering constraints are frequently used to break...
Combining Symmetry Breaking with Other Constraints: lexicographic ordering with sums (2004)
Brahim Hnich, Zeynep Kiziltan, Toby Walsh
We introduce a new global constraint which combines together the lexicographic ordering constraint with two sum constraints.
Symmetry Breaking Ordering Constraints (2004)
In a constraint satisfaction problem (CSP), symmetry involves the variables, values in the domains, or both, and maps each search state into an equivalent one. When searching for solutions,...
Combining symmetry breaking with other constraints: lexicographic ordering with sums (2004)
Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. We introduce a new global constraint which combines together the lexicographic ordering constraint with two sum constraints. Lexicographic ordering constraints are frequently used to break...
Multiset ordering constraints (2003)
Alan Frisch, Ian Miguel, Zeynep Kiziltan, Brahim Hnich, Toby Walsh
Zeynep.Kiziltan @ dis.uu. se {brahim,tw} @ 4c.ucc.ie We identify a new and important global (or nonbinary) constraint which ensures that the values taken by two vectors of variables, when viewed as...
Global constraints by composition: lexicographic ordering with sums (2003)
Brahim Hnich, Zeynep Kiziltan, Toby Walsh
Abstract. We introduce a new global constraint which combines together a lexicographic ordering constraint with some sum constraints. Applications for this constraint include balanced incomplete...
Multiset Ordering Constraints (2003)
Alan Frisch Dept, Alan Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel, Toby Walsh
We identify a new and important global (or non-binary) constraint. This constraint ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. This constraint is...
Multiset ordering constraints (2003)
Alan Frisch, Zeynep Kiziltan, Toby Walsh, Brahim Hnich, Ian Miguel
We identify a new and important global (or non-binary) constraint. This constraint ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. This constraint is...
Symmetry Breaking Ordering Constraints (2003)
Zeynep Kiziltan Computer, Zeynep Kiziltan
Introduction In a constraint satisfaction problem (CSP), symmetry involves the variables, values in the domains, or both, and maps each search state into an equivalent one. When searching for...
Multiset ordering constraints (2003)
Alan Frisch, Ian Miguel, Zeynep Kiziltan, Brahim Hnich, Toby Walsh
We identify a new and important global (or nonbinary) constraint which ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. This constraint is useful for...
Breaking row and column symmetries in matrix models (2002)
Pierre Flener, Alan M. Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel, Justin Pearson, ...
Breaking row and column symmetries in matrix models (2002)
Pierre Flener, Alan M. Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel, Justin Pearson, ...
Breaking row and column symmetries in matrix models (2002)
Pierre Flener, Alanm. Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel
Abstract. We identify an important class of symmetries in constraint programming, arising from matrices of decision variables where rows and columns can be swapped. Whilst lexicographically ordering...
Global Constraints for Lexicographic Orderings (2002)
Alan Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel, Toby Walsh
We propose some global constraintsf2 le icographic orderings on vectors of variables. These constraints are very usef lf5 breaking a certain kind of symmetry arising in matricesof decision variables....
Symmetry-breaking constraints for matrix models (2002)
Zeynep Kiziltan, Barbara M. Smith
Abstract. Many CSPs can be effectively represented and efficiently solved using matrix models, in which the matrices may have symmetry between their rows and/or columns. Eliminating all such symmetry...
Breaking row and column symmetries in matrix models (2002)
Pierre Flener, Alan M. Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel, Justin Pearson, ...
Constraint Programming with Multisets (2002)
Abstract. We propose extending constraint solvers with multiset variables. That is, variables whose values are multisets. Such an extension can help prevent introducing unnecessary symmetry into a...
Breaking row and column symmetries in matrix models (2002)
Pierre Flener, Alan M. Frisch, Brahim Hnich, Zeynep Kiziltan, Ian Miguel, Justin Pearson, ...
Compiling high-level type constructors in constraint programming (2001)
Pierre Flener, Brahim Hnich, Zeynep Kiziltan
Abstract. We propose high-level type constructors for constraint programming languages, so that constraint satisfaction problems can be modelled in very expressive ways. We design a practical set...
A Meta-Heuristic for Subset Decision Problems (2000)
Brahim Hnich, Zeynep Kiziltan, Pierre Flener
This paper is organised as follows. In Section 2, we discuss the class of subset decision problems and show the generic clp(FD) constraint store that results from such problems. Then, in Section 3,...
Towards Schema-Guided Compilation of Set Constraint Programs (1999)
Pierre Flener, Brahim Hnich, Zeynep Kiziltan
This paper is organised as follows. In Section 2, we discuss our set constraint programming language as well as (syntactic forms of programs of) the target language clp(FD). Then, in Section 3, we...