Browsing by Author "Bessiere, Christian"

Now showing 1 - 6 of 6

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: 26
Citation - Scopus: 32
The Complexity of Reasoning With Global Constraints
(Springer, 2007) Bessiere, Christian; Hebrard, Emmanuel; Hnich, Brahim; Walsh, Toby
Constraint propagation is one of the techniques central to the success of constraint programming. To reduce search, fast algorithms associated with each constraint prune the domains of variables. With global (or non-binary) constraints, the cost of such propagation may be much greater than the quadratic cost for binary constraints. We therefore study the computational complexity of reasoning with global constraints. We first characterise a number of important questions related to constraint propagation. We show that such questions are intractable in general, and identify dependencies between the tractability and intractability of the different questions. We then demonstrate how the tools of computational complexity can be used in the design and analysis of specific global constraints. In particular, we illustrate how computational complexity can be used to determine when a lesser level of local consistency should be enforced, when constraints can be safely generalized, when decomposing constraints will reduce the amount of pruning, and when combining constraints is tractable.
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: 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.