Pattern sampling has emerged as a promising approach for information discovery in large databases, allowing analysts to focus on a manageable subset of patterns. In this approach, patterns are randomly drawn based on an interestingness measure, such as frequency or hyper-volume. This paper presents the first sampling approach designed to handle interval patterns in numerical databases. This approach, named Fips , samples interval patterns proportionally to their frequency. It uses a multi-step sampling procedure and addresses a key challenge in numerical data: accurately determining the number of interval patterns that cover each object. We extend this work with HFips , which samples interval patterns proportionally to both their frequency and hyper-volume. These methods efficiently tackle the well-known long-tail phenomenon in pattern sampling. We formally prove that Fips and HFips sample interval patterns in proportion to their frequency and the product of hyper-volume and frequency, respectively. Through experiments on several databases, we demonstrate the quality of the obtained patterns and their robustness against the long-tail phenomenon.

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.

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.