Brahim Hnich

AIJ Journal 2015 Journal Article

Confidence-based reasoning in stochastic constraint programming

• Roberto Rossi
• Brahim Hnich
• S. Armagan Tarim
• Steven Prestwich

In this work we introduce a novel approach, based on sampling, for finding assignments that are likely to be solutions to stochastic constraint satisfaction problems and constraint optimisation problems. Our approach reduces the size of the original problem being analysed; by solving this reduced problem, with a given confidence probability, we obtain assignments that satisfy the chance constraints in the original model within prescribed error tolerance thresholds. To achieve this, we blend concepts from stochastic constraint programming and statistics. We discuss both exact and approximate variants of our method. The framework we introduce can be immediately employed in concert with existing approaches for solving stochastic constraint programs. A thorough computational study on a number of stochastic combinatorial optimisation problems demonstrates the effectiveness of our approach.

AIJ Journal 2012 Journal Article

Filtering algorithms for global chance constraints

• Brahim Hnich
• Roberto Rossi
• S. Armagan Tarim
• Steven Prestwich

Stochastic Constraint Satisfaction Problems (SCSPs) are a powerful modeling framework for problems under uncertainty. To solve them is a PSPACE task. The only complete solution approach to date — scenario-based stochastic constraint programming — compiles SCSPs down into classical CSPs. This allows the reuse of classical constraint solvers to solve SCSPs, but at the cost of increased space requirements and weak constraint propagation. This paper tries to overcome these drawbacks by automatically synthesizing filtering algorithms for global chance constraints. These filtering algorithms are parameterized by propagators for the deterministic version of the chance constraints. This approach allows the reuse of existing propagators in current constraint solvers and it has the potential to enhance constraint propagation. Our results show that, for the test bed considered in this work, our approach is superior to scenario-based stochastic constraint programming. For these instances, our approach is more scalable, it produces more compact formulations, it is more efficient in terms of run time and more effective in terms of pruning for both stochastic constraint satisfaction and optimization problems.

AAAI Conference 2011 Conference Paper

Extensible Automated Constraint Modelling

• Ozgur Akgun
• Ian Miguel
• Chris Jefferson
• Alan Frisch
• Brahim Hnich

In constraint solving, a critical bottleneck is the formulation of an effective constraint model of a given problem. The CONJURE system described in this paper, a substantial step forward over prototype versions of CONJURE previously reported, makes a valuable contribution to the automation of constraint modelling by automatically producing constraint models from their specifications in the abstract constraint specification language ESSENCE. A set of rules is used to re- fine an abstract specification into a concrete constraint model. We demonstrate that this set of rules is readily extensible to increase the space of possible constraint models CONJURE can produce. Our empirical results confirm that CONJURE can reproduce successfully the kernels of the constraint models of 32 benchmark problems found in the literature.

IJCAI Conference 2011 Conference Paper

Finding (α , ϑ )-Solutions via Sampled SCSPs

• Roberto Rossi
• Brahim Hnich
• S. Armagan Tarim
• Steven Prestwich

We discuss a novel approach for dealing with single-stage stochastic constraint satisfaction problems (SCSPs) that include random variables over a continuous or large discrete support. Our approach is based on two novel tools: sampled SCSPs and (α ,ϑ )-solutions. Instead of explicitly enumerating a very large or infinite set of future scenarios, we employ statistical estimation to determine if a given assignment is consistent for a SCSP. As in statistical estimation, the quality of our estimate is determined via confidence interval analysis. In contrast to existing approaches based on sampling, we provide likelihood guarantees for the quality of the solutions found. Our approach can be used in concert with existing strategies for solving SCSPs.

AIJ Journal 2009 Journal Article

Filtering algorithms for the multiset ordering constraint

• Alan M. Frisch
• Brahim Hnich
• Zeynep Kiziltan
• Ian Miguel
• Toby Walsh

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.

AIJ Journal 2009 Journal Article

Range and Roots: Two common patterns for specifying and propagating counting and occurrence constraints

• Christian Bessiere
• Emmanuel Hebrard
• Brahim Hnich
• Zeynep Kiziltan
• Toby Walsh

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.

ECAI Conference 2008 Conference Paper

SLIDE: A Useful Special Case of the CARDPATH Constraint

• Christian Bessière
• Emmanuel Hebrard
• Brahim Hnich
• Zeynep Kiziltan
• Toby Walsh

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.

AAAI Conference 2008 Conference Paper

The Parameterized Complexity of Global Constraints

• Christian Bessiere
• Brahim Hnich
• Claude-Guy Quimper

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 fixedparameter 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.

AIJ Journal 2006 Journal Article

Propagation algorithms for lexicographic ordering constraints

• 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 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.

IJCAI Conference 2005 Conference Paper

The Range and Roots Constraints: Specifying Counting and Occurrence Problems

• Christian Bessiere
• Emmanuel Hebrard
• Brahim Hnich
• Zeynep Kiziltan
• Toby

We propose a simple declarative language for specifying a wide range of counting and occurrence constraints. This specification language is executable since it immediately provides a polynomial propagation algorithm. To illustrate the capabilities of this language, we specify a dozen global constraints taken from the literature. We observe one of three outcomes: we achieve generalized arc-consistency; we do not achieve generalized arc-consistency, but achieving generalized arcconsistency is NP-hard; we do not achieve generalized arc-consistency, but specialized propagation algorithms can do so in polynomial time. Experiments demonstrate that this specification language is both efficient and effective in practice.

ECAI Conference 2004 Conference Paper

Robust Solutions for Constraint Satisfaction and Optimization

• Emmanuel Hebrard
• Brahim Hnich
• Toby Walsh

AAAI Conference 2004 Conference Paper

The Complexity of Global Constraints

• Christian Bessiere
• Brahim Hnich

We study the computational complexity of reasoning with global constraints. We show that reasoning with such constraints is intractable in general. We then demonstrate how the same 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 decomposing constraints will lose pruning, and when combining constraints is tractable. We also show how the same tools can be used to study symmetry breaking, meta-constraints like the cardinality constraint, and learning nogoods.

IJCAI Conference 2003 Conference Paper

Multiset Ordering Constraints

• 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 a number of different applications including breaking symmetry and fuzzy constraint satisfaction. We propose and implement a linear time algorithm for enforcing generalised arc-consistency on such a multiset ordering constraint. Experimental results show considerable promise.

LOPSTR Conference 1990 Conference Paper

Schema-Guided Synthesis of CLP Programs

• Hamza Zidoum
• Pierre Flener
• Brahim Hnich

Abstract This work is inspired by D. R. Smith’s research on synthesising global search (GS) programs (in the Refine language) from first-order logic specifications (also in Refine) [ 8, 9, 10 ]. We concentrate on synthesising constraint logic programs (CLP) [ 6 ] instead. We thus only have to synthesise code that (incrementally) poses the constraints, because the actual constraint propagation and pruning are performed by the CLP system. We here only tackle the family of decision assignment problems; the families of optimisation assignment problems, decision permutation problems, and optimisation permutation problems are covered in [ 4 ].