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.

In Model-Driven Engineering (MDE), the Unified Modeling Language (UML) is often combined with the Object Constraint Language (OCL) to express constraints on models. While these constraints are typically used for validation, certain tasks-such as model search, completion, repair, or exploration–require the automatic generation of models that satisfy them. Due to the combinatorial nature of these tasks, even small models can lead to computationally complex problems. Constraint Programming (CP) offers a powerful paradigm for modeling and solving such combinatorial challenges, notably through the use of global constraints, which enable concise models supported by efficient algorithms. Although previous approaches have tackled model search using tools like Alloy or ATLc, they often rely on simplified subsets or avoid the use of global constraints. In this paper, we extend the ATLc approach by leveraging CP to the expressiveness and coverage of UML/OCL. We introduce a CP model for representing UML instances and evaluating queries, along with global constraint formulations for UML collection types (Sequence, Bag, Set, OrderedSet) and their corresponding OCL type casting operations (asSequence, asBag, asSet and asOrderedSet). Finally we provide an implementation allowing us to test our model for this subset of OCL and compare with related work.

Constrained clustering algorithms integrate user knowledge as constraints in the clustering process to guide it towards a desired outcome. When interacting with users, it is essential to quickly ask simple questions to identify informative constraints that will efficiently enhance an initial partition. We propose a new active query strategy for incremental clustering that translates user feedback into interpretable decision rules and identifies relevant points for queries using rule-based heuristics Experiments on benchmark datasets highlight the benefits of our new approach, making it suitable for real-world applications.

Clustering is a well-known task in Data Mining that aims at grouping data instances according to their similarity. It is an exploratory and unsupervised task whose results depend on many parameters, often requiring the expert to iterate several times before satisfaction. Constrained clustering has been introduced for better modeling the expectations of the expert. Nevertheless constrained clustering is not yet sufficient since it usually requires the constraints to be given before the clustering process. In this paper we address a more general problem that aims at modeling the exploratory clustering process, through a sequence of clustering modifications where expert constraints are added on the fly. We present an incremental constrained clustering framework integrating active query strategies and a Constraint Programming model to fit the expert expectations while preserving the stability of the partition, so that the expert can understand the process and apprehend its impact. Our model supports instance and group-level constraints, which can be relaxed. Experiments on reference datasets and a case study related to the analysis of satellite image time series show the relevance of our framework.

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.

In this paper, we propose an improvement of the compression step of sliced table method proposed by Gharbi et al. [1] for compressing and solving table constraints. We consider only n-ary CSP defined in extensional form. More precisely, we propose to use the cover of an itemset in the FP-tree instead of its frequency to improve the construction step of the resulting compressed tables. Moreover, we propose to exploit the compression rate metric instead of savings to compute frequent itemsets relevant for compression. This allows higher compression and leads to an efficient resolution of compressed tables by identifying more accurate frequent itemsets necessary for compression. Experimental results show the effectiveness and efficiency of our approach.

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.

We introduce the notion of Optimal Patterns (OPs), defined as the best patterns according to a given user preference, and show that OPs encompass many data mining problems. Then, we propose a generic method based on a Dynamic Constraint Satisfaction Problem to mine OPs, and we show that any OP is characterized by a basic constraint and a set of constraints to be dynamically added. Finally, we perform an experimental study comparing our approach vs adhoc methods on several types of OPs.

We introduce skypattern cubes and propose an efficient bottom-up approach to compute them. Our approach relies on derivation rules collecting skypatterns of a parent node from its child nodes without any dominance test. Non-derivable skypatterns are computed on the fly thanks to Dynamic CSP. The bottom-up principle enables to provide a concise representation of the cube based on skypattern equivalence classes without any supplementary effort. Experiments show the effectiveness of our proposal.

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.

We propose an effective method to compute the sky pattern cubes thanks to a relaxation strategy in the pattern mining process. Our approach is based on the fact that each node of the cube can be approximated by the set of edge-sky patterns (a relaxed form of sky patterns) w.r.t. The whole set of measures M. Then we transform the problem into a skyline cube mining in M dimensions. The set of edge-sky patterns can be efficiently mined by using either a dynamic CSP method or an extended version of a static method based on the theoretical relationships between patterns and condensed representations of sky patterns. Experiments conducted on UCI datasets and on a real-life dataset (Mutagen city) show the relevance and performance of our approach.

As (Lee et al., 2012) have shown, weighted constraint satisfaction problems can benefit from the introduction of global cost functions, leading to a new Cost Function Programming paradigm. In this paper, we explore the possibility of decomposing global cost functions in such a way that enforcing soft local consistencies on the decomposition offers guarantees on the level of consistency enforced on the original global cost function. We show that directional arc consistency and virtual arc consistency offer such guarantees. We conclude by experiments on decomposable cost functions showing that decompositions may be very useful to easily integrate efficient global cost functions in solvers.

Tree decomposition introduced by Robertson and Seymour aims to decompose a problem into clusters constituting an a cyclic graph. There are works exploiting tree decomposition for complete search methods. In this paper, we show how tree decomposition can be used to efficiently guide the exploration of local search methods that use large neighborhoods like VNS. We introduce tightness dependent tree decomposition which allows to take advantage of both the structure of the problem and the constraints tightness. Experiments performed on random instances (GRAPH) and real life instances (CELAR and SPOT5) show the appropriateness and the efficiency of our approach.

In this paper, we propose a new value ordering heuristic for weighted constraint satisfaction problems (WCSP) based on the quality of solutions. The H-quality of an assignment estimates its capacity at occurring in solutions of "good" quality. Experiments using limited discrepancy search on random WCSP instances and CELAR benchmarks show that our value ordering always outperforms MinAC in a significant way.

A soft version of the well-known global constraint AllDifferent has been recently introduced for the Max-CSP framework ([9, 15, 16]). In this paper, we propose to soften AllDifferent in the Weighted CSP framework that is more general. We extend the two semantics of violation proposed in [9]: the first one is based on variables and the second one on the decomposition into a set of binary constraints of difference. For the first semantic, we propose a polynomial algorithm which maintains hyper- arc consistency. For the second one, we prove that checking hyper-arc consistency is an NP-Hard problem. So, we propose to maintain a local consistency using a filtering based on lower bounds computation. Finally, we present some experimental results and draw a few perspectives.

This paper describes a new hybrid method for solving constraint optimization problems in anytime contexts. We use the valued constraint satisfaction problem (VCSP) framework to model numerous discrete optimization problems. Our method (VNS/LDS+CP) combines a variable neighborhood search (VNS) scheme with limited discrepancy search (LDS) using constraint propagation (CP) to evaluate cost and legality of moves made by VNS. Experiments on real-word problem instances demonstrate that our method clearly outperforms both LNS/CP/GR and other standard local search methods as simulated annealing.