Browsing by Author "Kiziltan Z."

Now showing 1 - 3 of 3

Citation - Scopus: 24
The Parameterized Complexity of Global Constraints
(2008) Bessiere C.; Hebrard E.; Hnich B.; Kiziltan Z.; Quimper C.-G.; Walsh T.
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 natural parameters which make them fixed-parameter tractable and which are easy to compute. This tractability tends either to be the result of a simple dynamic program or of a decomposition which has a strong backdoor of bounded size. This strong backdoor is often a cycle cutset. We also show that parameterized complexity can be used to study other aspects of constraint programming like symmetry breaking. For instance, we prove that value symmetry is fixed-parameter tractable to break in the number of symmetries. Finally, we argue that parameterized complexity can be used to derive results about the approximability of constraint propagation. Copyright © 2008, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Citation - Scopus: 14
Reformulating Global Constraints: the Slide and Regular Constraints
(Springer Verlag, 2007) Bessiere C.; Hebrard E.; Hnich B.; Kiziltan Z.; Quimper C.-G.; Walsh T.
Global constraints are useful for modelling and reasoning about real-world combinatorial problems. Unfortunately, developing propagation algorithms to reason about global constraints efficiently and effectively is usually a difficult and complex process. In this paper, we show that reformulation may be helpful in building such propagators. We consider both hard and soft forms of two powerful global constraints, SLIDE and REGULAR. These global constraints are useful to represent a wide range of problems like rostering and scheduling where we have a sequence of decision variables and some constraint that holds along the sequence. We show that the different forms of SLIDE and REGULAR can all be reformulated as each other. We also show that reformulation is an effective method to incorporate such global constraints within an existing constraint toolkit. Finally, this study provides insight into the close relationship between these two important global constraints. © Springer-Verlag Berlin Heidelberg 2007.
Citation - Scopus: 32
Slide: a Useful Special Case of the Cardpath Constraint
(IOS Press, 2008) Bessiere C.; Hebrard E.; Hnich B.; Kiziltan Z.; Walsh T.
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 hold always, can be used to encode a wide range of sliding sequence constraints including CARDPATH itself. We consider how to propagate SLIDE and provide a complete propagator for CARDPATH. Since propagation is NP-hard in general, we identify special cases where propagation takes polynomial time. Our experiments demonstrate that using SLIDE to encode global constraints can be as efficient and effective as specialised propagators. © 2008 The authors and IOS Press. All rights reserved.