A cryptarithm is a mathematical and logical puzzle in which words form an equation where the letters represent numbers to be determined in a given base. This problem is popular in recreational mathematics, education, and constraint programming. We propose a general, efficient and easy-to-use approach to solve this NP-Complete problem, as well as a hierarchical approach for their generation. The experimental evaluation has generated a large, diverse, and remarkable collection of new cryptarithms.

The maximal clique enumeration (MCE) problem consists of computing and listing all maximal cliques in a finite graph. The problem is NP-complete since it subsumes the classic version of the NP-complete clique decision problem. The most well-known algorithm to solve this problem has been proposed by Bron & Kerbosch (BK). Generalizing this algorithm to hypergraphs presents significant challenges and admits multiple solutions. The primary difficulty stems from the fundamental difference in structure: while in standard graphs a vertex has a bounded number of incident edges, in hypergraphs a vertex can participate in an exponential number of hyperedges. Specifically, in a hypergraph with$n$vertices where hyperedges have arity$r$, a single vertex may belong to up to$\binom{n-1}{r-1}$hyperedges. This structural complexity renders the direct generalization of BK computationally inefficient. In this article, we propose three new approaches to solve the MHE problem. First, a relaxation method based on the relaxation of a hypergraph in a graph. Then, a method based on an efficiently computation of the hypercliques containing a set of vertices. Finally, a method combining the previous ones. We conducted an experimental study on a set of benchmarks, showing one or two orders of magnitude performance improvements of our approach with regards to the direct generalization of BK to hypergraphs.

In robust optimization, finding a solution that solely respects the constraints is not enough. Usually, the uncertainty and unknown parameters of the model are represented by random variables. In such conditions, a good solution is a solution robust to most-likely assignments of these random variables. Recently, the Confidence constraint has been introduced by Mercier-Aubin et al. in order to enforce this type of robustness in constraint programming. Unfortunately, it is restricted to a conjunction of binary inequalities In this paper, we generalize the Confidence constraint to any constraint and propose an implementation based on Multi-valued Decision Diagrams (MDDs). The Confidence constraint is defined over a vector of random variables. For a given constraint C, and given a threshold, the Confidence constraint ensures that the probability for C to be satisfied by a sample of the random variables is greater than the threshold. We propose to use MDDs to represent the constraints on the random variables. MDDs are an efficient tool for representing combinatorial constraints, thanks to their exponential compression power. Here, both random and decision variables are stored in the MDD, and propagation rules are proposed for removing values of decision variables that cannot lead to robust solutions. Furthermore, for several constraints, we show that decision variables can be omitted from the MDD because lighter filtering algorithms are sufficient. This leads to gain an exponential factor in the MDD size. The experimental results obtained on a chemical deliveries problem in factories – where the chemicals consumption are uncertain – shows the efficiency of the proposed approach.

Multi-objective problems are frequent in the real world. In general they involve several incomparable objectives and the goal is to find a set of Pareto optimal solutions, i.e. solutions that are incomparable two by two. In order to better deal with these problems in CP the global constraint Pareto was developed by Schaus and Hartert to handle the relations between the objective variables and the current set of Pareto optimal solutions, called the archive. This constraint handles three operations: adding a new solution to the archive, removing solutions from the archive that are dominated by a new solution, and reducing the bounds of the objective variables. The complexity of these operations depends on the size of the archive. In this paper, we propose to use a multi-valued Decision Diagram (MDD) to represent the archive of Pareto optimal solutions. MDDs are a compressed representation of solution sets, which allows us to obtain a compressed and therefore smaller archive. We introduce several algorithms to implement the above operations on compressed archives with a complexity depending on the size of the archive. We show experimentally on bin packing and multi-knapsack problems the validity of our approach.

International audience