Constraint-based pattern mining is at the core of numerous data mining tasks. Usually, pattern mining problems are handled as constraint-solving tasks. However, in practice, the resulting patterns are often large, and selecting appropriate thresholds for these constraints can be challenging. This paper addresses these issues by expanding data mining algorithms into the realm of optimization, treating the task as one of identifying the best patterns according to a set of objective functions. We explore a multi-objective optimization approach, where several potentially conflicting objectives are optimized simultaneously. In the absence of preferences, Pareto dominance is commonly used to identify optimal compromise solutions. We present a novel Constraint Programming model designed to efficiently mine Pareto optimal patterns. Our model leverages condensed pattern representations to reduce computational effort and introduces a new global constraint to enforce the closure of patterns across multiple measures. We demonstrate the application of our approach to derive high-quality frequent and (rare) non-redundant association rules without relying on threshold values. The effectiveness of our approach is validated using both UCI datasets and a case study involving gene expression analysis, integrating multiple external gene annotations.

Constraint-based pattern mining is at the core of numerous data mining tasks. Unfortunately, thresholds which are involved in these constraints cannot be easily chosen. This paper investigates a Multi-objective Optimization approach where several (often conflicting) functions need to be optimized at the same time. We introduce a new model for efficiently mining Pareto optimal patterns with constraint programming. Our model exploits condensed pattern representations to reduce the mining effort. To this end, we design a new global constraint for ensuring the closeness of patterns over a set of measures. We show how our approach can be applied to derive high-quality non redundant association rules without the use of thresholds whose added-value is studied on both UCI datasets and case study related to the analysis of genes expression data integrating multiple external genes annotations.

Graphical models factorize a global probability distribution/energy function as the product/ sum of local functions. A major inference task, known as MAP in Markov Random Fields and MPE in Bayesian Networks, is to find a global assignment of all the variables with maximum a posteriori probability/minimum energy. A usual distinction on MAP solving methods is complete/incomplete, i.e. the ability to prove optimality or not. Most complete methods rely on tree search, while incomplete methods rely on local search. Among them, we study Variable Neighborhood Search (VNS) for graphical models. In this paper, we propose an iterative approach above VNS that uses (partial) tree search inside its local neighborhood exploration. The proposed approach performs several neighborhood explorations of increasing search complexity, by controlling two parameters, the discrepancy limit and the neighborhood size. Thus, optimality of the obtained solutions can be proven when the neighborhood size is maximal and with unbounded tree search. We further propose a parallel version of our method improving its anytime behavior on difficult instances coming from a large graphical model benchmark. Last we experiment on the challenging minimum energy problem found in Computational Protein Design, showing the practical benefit of our parallel version. A solver is available at https://github.com/toulbar2/toulbar2.

Cryptographic protocols form the backbone of digital society. They are concurrent multiparty communication protocols that use cryptography to achieve security goals such as confidentiality, authenticity, integrity, etc., in the presence of adversaries. Unfortunately, protocol verification still represents a critical task and a major cost to engineer attack-free security protocols. Model checking and SAT-based techniques proved quite effective in this context. This article proposes an efficient automatic model checking approach that exemplifies a security property violation. In this approach, a protocol verification is abstracted as a compact planning problem, which is efficiently solved by a state-of-the-art SAT solver. The experiments performed on some real-world cryptographic protocols succeeded in detecting new logical attacks, violating some security properties. Those attacks encompass both “type flaw” and “replay” attacks, which are difficult to tackle with the existing planning-based approaches.

Fault localization problem is one of the most difficult processes in software debugging. The current constraint-based approaches draw strength from declarative data mining and allow to consider the dependencies between statements with the notion of patterns. Tackling large faulty programs is clearly a challenging issue for Constraint Programming (CP) approaches. Programs with multiple faults raise numerous issues due to complex dependencies between faults, making the localization quite complex for all of the current localization approaches. In this paper, we provide a new CP model with a global constraint to speed-up the resolution and we improve the localization to be able to tackle multiple faults. Finally, we give an experimental evaluation that shows that our approach improves on CP and standard approaches.

Sequential pattern mining under various constraints is a challenging data mining task. The paper provides a generic framework based on constraint programming to discover sequence patterns defined by constraints on local patterns (e.g., Gap, regular expressions) or constraints on patterns involving combination of local patterns such as relevant subgroups and top-k patterns. This framework enables the user to mine in a declarative way both kinds of patterns. The solving step is done by exploiting the machinery of Constraint Programming. For complex patterns involving combination of local patterns, we improve the mining step by using dynamic CSP. Finally, we present two case studies in biomedical information extraction and stylistic analysis in linguistics.

Constraint programs, such as those written in high-level constraint modelling languages, e.g., OPL (Optimization Programming Language), COMET, ZINC or ESSENCE, are more and more used in business-critical programs. As any other critical programs, they require to be thoroughly tested and corrected to prevent catastrophic loss of money. This paper 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.

Constraint programs such as those written in high level modeling languages (e.g., OPL, ZINC, or COMET) must be thoroughly verified before being used in applications. Detecting and localizing faults is therefore of great importance to lower the cost of the development of these constraint programs. In a previous work, we introduced a testing framework called CPTEST enabling automated test case generation for detecting non-conformities. In this paper, we enhance this framework to introduce automatic fault localization in constraint programs. Our approach is based on constraint relaxation to identify the constraint that is responsible of a given fault. CPTEST is henceforth able to automatically localize faults in optimized OPL programs. We provide empirical evidence of the effectiveness of this approach on classical benchmark problems, namely Golomb rulers, n-queens, social golfer and car sequencing.