Hybridization of CP and SAT combines the strengths of both paradigms, Constraint Programming (CP) and the Boolean satisfiability problem (SAT). This hybridization allows for the use of dedicated CP propagators paired with the powerful clause learning mechanism of SAT. In contrast to lazy clause generation, solvers based on lazy explanations extract a SAT explanation after each conflict and in particular after those detected by a CP propagator. In this article, we rely on a constraint-wise generic explanation algorithm to build new ad hoc explanation and reason extracting algorithms for the Sum constraint and some of its variants. Time complexity concerns fueled the elaboration of a relaxed version of our ad hoc algorithms, where the loss of a reasonable amount of clause accuracy yields better results. Finally, we conduct an empirical study on XCSP3 instances, where the efficiency of our ad hoc algorithms in reducing the size of generated clauses is clearly visible.

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.

In this paper, we propose a model to schedule the next 24 hours of operations in a bulk cargo port to unload bulk cargo trains onto stockpiles. It is a problem that includes multiple parts such as splitting long trains into shorter ones and the routing of bulk material through a configurable network of conveyors to the stockpiles. Managing such trains (up to three kilometers long) also requires specialized equipment. The real world nature of the problem specification implies the necessity to manage heterogeneous data. Indeed, when new equipment is added (e.g. dumpers) or a new type of wagon comes in use, older or different equipment will still be in use as well. In this paper, we provide a detailed presentation of this real world problem and its associated data. This allows us to propose an effective constraint programming model to solve this problem. We also discuss the model design and the different implementations of the propagators that we used in practice. Finally, we show how this model, coupled with a large neighborhood search, was able to find 24 hour schedules efficiently

Heuristics are one of the most important tools to guide search to solve combinatorial problems. They are often specifically designed for one single problem and require both expertise and implementation work. Generic frameworks like SAT or CSP have developed heuristics that obey general principles like first fail or are able to learn and adapt from the exploration of the search tree like Dom/wDeg. In SAT, the classic VSIDS heuristic falls into both categories. The question of whether it is possible to learn from solving existing problems has been addressed for a long time by portfolio solvers where the best heuristic is chosen by Machine Learning from hand-crafted features, and more recently with Deep Learning by embedding this knowledge into a Graph Neural Network (GNN). In this paper, we build upon the latter category by proposing a new heuristic based on Deep Reinforcement Learning using two GNNs with adversarial rewards. We show that our method reduces the number of fails to get the first solution by more than 50% compared to MiniSat. This work shows the advantages of this type of techniques to extract structural and contextual knowledge from past solving experience.

Software Defined Networking (or SDN) allows to apply a centralized control over a network of computers in order to provide better global throughput. One of the problem to solve is the multi-commodity flow routing where a set of demands (or commodities) have to be routed at minimum cost. In contrast with other versions of this problem, we consider here problems with congestion that change the cost of a link according to the capacity used. We propose here to study centralized routing with Constraint Programming and selfish routing with Constraint Games. Selfish routing reaches a Nash equilibrium and is important for the perceived quality of the solution since no user is able to improve his cost by changing only his own path. We present real and synthetic benchmarks with hundreds or thousands players and we show that for this problem the worst selfish routing is often close to the optimal centralized solution.

Constraint Games are a recent framework proposed to model and solve static games where Constraint Programming is used to express players preferences. In this paper, we rethink their solving technique in terms of constraint propagation by considering players preferences as global constraints. It yields not only a more elegant but also a more efficient framework. Our new complete solver is faster than previous state-of-the-art and is able to find all pure Nash equilibria for some problems with 200 players. We also show that performances can greatly be improved for graphical games, allowing some games with 2000 players to be solved.

Game theory is a highly successful paradigm for strategic decision making between multiple agents having conflicting objectives. Since a few years, games have been studied in a computational perspective, raising new issues like complexity of equilibria or succinctness of representation. Indeed, the main representation for general games is still a n-dimensional matrix of exponential size called normal form. In this paper, we introduce the framework of Constraint Games to model strategic interaction between players. A Constraint Game is composed of a set of variables shared by all the players. Among these variables, each player owns a set of decision variables she can control and a Constraint Optimization Problem defining her preferences. Since the preferences of a player depend on the decisions taken by the other players, each player may try to improve her position by choosing an assignment that optimizes her preferences. Pure Nash equilibria are situations in which no player may improve her preferences unilaterally. Constraint Games are thus a generic tool to model general games and can be exponentially more succinct than their normal form. We show the practical utility of the framework by modelling a few realistic problems and we propose an algorithm based on tabu search to compute pure Nash equilibria in Constraint games that outperforms the algorithms based on normal form. In addition, Constraint Games raise some interesting research issues that deserve further attention.

It is well known that modeling with constraints networks require a fair expertise. Thus tools able to automatically generate such networks have gained a major interest. The major contribution of this paper is to set a new framework based on Inductive Logic Programming able to build a constraint model from solutions and non-solutions of related problems. The model is expressed in a middle-level modeling language. On this particular relational learning problem, traditional top-down search methods fall into blind search and bottom-up search methods produce too expensive coverage tests. Recent works in Inductive Logic Programming about phase transition and crossing plateau shows that no general solution can face all these difficulties. In this context, we have designed an algorithm combining the major qualities of these two types of search techniques. We present experimental results on some benchmarks ranging from puzzles to scheduling problems.

Quantified constraint satisfaction problems have been the topic of an increasing number of studies for a few years. However, only sequential resolution algorithms have been proposed so far. This paper presents a parallel QCSP+ solving algorithm based on a problem-partition approach. It then discuss about work distribution policies and presents several experimental results comparing several parameters.

Partially defined constraints can be used to model the incomplete knowledge of a concept or a relation. Instead of only computing with the known part of the constraint, we propose to complete its definition by using machine learning techniques. Since constraints are actively used during solving for pruning domains, building a classifier for instances is not enough: we need a solver able to reduce variable domains. Our technique is composed of two steps: first we learn a classifier for the constraint's projections and then we transform the classifier into a propagator. We show that our technique not only has good learning performances but also yields a very efficient solver for the learned constraint.