Browsing by Author "Kiziltan, Zeynep"

Now showing 1 - 7 of 7

Citation - WoS: 5
Citation - Scopus: 13
Among, Common and Disjoint Constraints
(Springer-Verlag Berlin, 2006) Bessiere, Christian; Hebrard, Emmanuel; Hnich, Brahim; Kiziltan, Zeynep; Walsh, Toby
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 show how computational complexity can be used to determine whether achieving the highest level of consistency is tractable. For tractable constraints, we present a polynomial propagation algorithm and compare it to logical decompositions with respect to the amount of constraint propagation. For intractable cases, we show in many cases that a propagation algorithm can be adapted from a propagation algorithm of a similar tractable one.
Citation - WoS: 4
Citation - Scopus: 7
Filtering Algorithms for the Multiset Ordering Constraint
(Elsevier, 2009) Frisch, Alan M.; 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 of the important factors behind the success of CP. In this paper, we study a new global constraint, the multiset ordering constraint, which is shown to be useful in symmetry breaking and searching for leximin optimal solutions in CP. We propose efficient and effective filtering algorithms for propagating this global constraint. We show that the algorithms maintain generalised arc-consistency and we discuss possible extensions. We also consider alternative propagation methods based on existing constraints in CP toolkits. Our experimental results on a number of benchmark problems demonstrate that propagating the multiset ordering constraint via a dedicated algorithm can be very beneficial. (C) 2008 Elsevier B.V. All rights reserved.
Citation - WoS: 25
Citation - Scopus: 34
Filtering Algorithms for the Nvalue Constraint
(Springer, 2006) Bessiere, Christian; Hebrard, Emmanuel; Hnich, Brahim; Kiziltan, Zeynep; Walsh, Toby
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 even the lower bound on the number of values is NP-hard. We therefore study different approximation heuristics for this problem. We introduce three new methods for computing a lower bound on the number of values. The first two are based on the maximum independent set problem and are incomparable to a previous approach based on intervals. The last method is a linear relaxation of the problem. This gives a tighter lower bound than all other methods, but at a greater asymptotic cost.
Citation - WoS: 25
Citation - Scopus: 34
Propagation Algorithms for Lexicographic Ordering Constraints
(Elsevier, 2006) Frisch, Alan M.; Hnich, Brahirn; Kiziltan, Zeynep; Miguel, Ian; Walsh, Toby
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 problem, it is modelled by a set of constraints on a set of decision variables. A common modelling pattern is the use of matrices of decision variables. The rows and/or columns of these matrices are often symmetric, leading to redundancy in a systematic search for solutions. An effective method of breaking this symmetry is to constrain the assignments of the affected rows and columns to be ordered lexicographically. This paper develops an incremental propagation algorithm, GACLexLeq, that establishes generalised arc consistency on this constraint in O(n) operations, where n is the length of the vectors. Furthermore, this paper shows that decomposing GACLexLeq into primitive constraints available in current finite-domain constraint toolkits reduces the strength or increases the cost of constraint propagation. Also presented are extensions and modifications to the algorithm to handle strict lexicographic ordering, detection of entailment, and vectors of unequal length. Experimental results on a number of domains demonstrate the value of GACLexLeq. (c) 2006 Elsevier B.V. All rights reserved.
Citation - WoS: 8
Citation - Scopus: 12
Range and Roots: Two Common Patterns for Specifying and Propagating Counting and Occurrence Constraints
(Elsevier, 2009) 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 patterns. Counting and occurrence constraints specified using these patterns thus directly inherit a propagation algorithm. To illustrate the capabilities of the RANGE and ROOTS constraints, we specify a number of global constraints taken from the literature. Preliminary experiments demonstrate that propagating counting and occurrence constraints using these two patterns leads to a small loss in performance when compared to specialised global constraints and is competitive with alternative decompositions using elementary constraints. (C) 2009 Elsevier B.V. All rights reserved.
Citation - WoS: 1
Citation - Scopus: 3
The Range Constraint: Algorithms and Implementation
(Springer-Verlag Berlin, 2006) Bessiere, Christian; Hebrard, Emmanuel; Hnich, Brahim; Kiziltan, Zeynep; Walsh, Toby
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 computes the range of values used by a set of variables, and the ROOTS constraint, which computes the variables mapping onto particular values. In order for this specification language to be executable, propagation algorithms for the RANGE and ROOTS constraints should be developed. In this paper, we focus on the study of the RANGE constraint. We propose an efficient algorithm for propagating the RANGE constraint. We also show that decomposing global counting and occurrence constraints using RANGE is effective and efficient in practice.
Citation - WoS: 2
Citation - Scopus: 5
The Roots Constraint
(Springer-Verlag Berlin, 2006) Bessiere, Christian; Hebrard, Emmanuel; Hnich, Brahim; Kiziltan, Zeynep; Walsh, Toby
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 variables, and the ROOTS constraint, which computes the variables mapping onto a set of values. We focus here on the ROOTS constraint. We show that propagating the ROOTS constraint completely is intractable. We therefore propose a decomposition which can be used to propagate the constraint in linear time. Interestingly, for all uses of the ROOTS constraint we have met, this decomposition does not destroy the global nature of the constraint as we still prune all possible values. In addition, even when the ROOTS constraint is intractable to propagate completely, we can enforce bound consistency in linear time simply by enforcing bound consistency on the decomposition. Finally, we show that specifying counting and occurrence constraints using ROOTS is effective and efficient in practice on two benchmark problems from CSPLib.