Constraint programming (modeling, constraint acquisition, Global constraints, elicitation based solvers, constraint negation)
Declarative Data mining (Constraint based itemset mining, Constraint based clustering, Constraint based sequence mining)
Verification & validation in CP (conformity testing, mutation, fault localization, automatic correction)
SAT solving (Modern SAT solvers,parallel SAT solving, portfolio SAT solvers)
Machine Learning (Multi-Armed Bandit problem, Monte Carlo Search Tree (MCTS))
Constraint programming is used to model and to solve complex combinatorial problems. The modeling task requires some expertise in constraint programming. This requirement is a bottleneck to the broader uptake of constraint technology. Several approaches have been proposed to assist
the non-expert user in the modelling task. Our works present the basic architecture for acquiring constraint networks from examples classified by the user. The theoretical questions raised by constraint acquisition are stated and their complexity is given. We then propose Conacq, a system that uses a concise representation of the learner’s version space into a clausal formula. Based on this logical representation, our architecture uses strategies for eliciting constraint networks in both the passive acquisition context, where the learner is only provided a pool of examples, and the active acquisition context, where the learner is allowed to ask membership queries to the user. The computational properties of our strategies are analyzed and their practical effectiveness is experimentally evaluated. We also introduce QUACQ for Quick Aqcuisition where we learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm that, given a negative example, focuses onto a constraint of the target network in a number of queries logarithmic in the size of the example. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases.
Discovering the set of closed frequent patterns is one of the fundamental problems in Data Mining. Recent Constraint Programming (CP) approaches for declarative itemset mining have proven their usefulness and flexibility. But the wide use of reified constraints in current CP approaches raises many difficulties to cope with high dimensional datasets. This paper proposes ClosedPattern global constraint which does not require any reified constraints nor any extra variables to encode efficiently the Closed Frequent Pattern Mining (CFPM) constraint.
ClosedPattern captures the particular semantics of the CFPM problem in order to ensure domain consistency using a polynomial pruning algorithm. That is, ClosedPattern guarantees to produce closed patterns in a backtrack-free manner. The computational properties of our constraint are analyzed and their practical effectiveness are experimentally evaluated
In our previous work [CP10 and Constraints12], we introduced a testing framework where a first highly declarative constraint model is taken as a reference to detect non-conformities within a refined and optimized constraint program solving the same problem. These non-conformities result from faults introduced during the refinement process, coming either from the absence or the bad formulation of constraints.
In [ICTAI10], we address the problem of automatically locating the constraint that is responsible of such a non-conformity. We introduce a fault localization approach that is fully automated for OPL programs. This approach is based on systematic constraint relaxation by making use of the ILOG CP constraint solver. The idea is to solve auxiliary constraint programs built over the OPL constraint program under test and the reference model used to specify the problem. We provide an algorithm that takes the faulty constraint program and a non-conformity as inputs and returns either a single constraint or a set of constraints that are responsible of the fault.
In [ICST11], we presents a framework for the automatic correction of constraint programs that takes into account the specificity of the software development process of these programs as well as their typical faults. We implemented this framework in our testing platform CPTEST for OPL programs. Using mutation testing, our experimental results show that well-known constraint programs written in OPL can be automatically corrected using our framework.
We introduce in this work an itemset mining approach to tackle the fault localization problem, which is one of the most difficult processes in software debugging. We formalize the problem of fault localisation as finding the k best patterns satisfying a set of constraints modelling the most suspicious statements. We use a Constraint Programming (CP) approach to model and to solve our itemset based fault localization problem. Our approach consists of two steps: i) mining top-k suspicious suites of statements; ii) fault localization by processing top-k patterns. Experiments performed on standard benchmark programs show that our approach enables to propose a more precise localization than a standard approach.
In recent years, Parallel SAT solvers have leveraged with the so called Parallel Portfolio architecture. In this setting, a collection of independent Conflict-Directed Clause Learning (CDCL) algorithms compete and cooperate through Clause Sharing. However, when the number of processing units increases, systematic clause sharing between CDCLs can slow down the search performance. Previous work has shown how the efficiency of the approach can be improved through controlling dynamically the amount of information shared by the cores [18], specifically the allowed length of the shared clauses. In my current work, a new approach is used to control both the cooperation topology (pairs of units able to exchange clauses) and the allowed length of the shared clauses. This approach, referred to as Bandit Ensemble for parallel SAT Solving (BESS), relies on a multi-armed bandit formalization of the cooperation choices.
