Algorithms for Inference and Constraints

The thesis objective is to solve combinatorial problems, typically optimization ones, by managing two sides still not exploited nowadays: the distributed nature of the solving context and the growing size of problems. Some problems, for security and/or confidentiality reasons need to be handled by distributing solving. The size of some problems can be a reason to need a division between several communicating agents. In this thesis, we will be interested in information exchanges between agent which have a total or partial knowledge of the constraint problem to solve. In particular, we will answer these three fundamental questions: what information can be exchanged? When exchanging it? And under which form? Some problems, in particular those related to digital technology, have a humongous size, for example social networks or data related to recommendation systems. The second part of the thesis is about constraint compilation into compact structure and/or constraints reformulation by searching partial semantic elements that can be combined. Finally, we consider an application of our work to the mobilization and distributed solving of realist combinatorial problems (we already have data for recommendation systems) with tools developed during the thesis.

See on theses.fr See on CRIL website

Gael Glorian, Jean-Marie Lagniez, Valentin Montmirail, and Michael Sioutis.
**An Incremental Sat-Based Approach to Reason Efficiently on Qualitative Constraint Networks**. In John Hooker,
editor, *Principles and Practice of Constraint Programming
*, pages 160--178, Cham, 2018. Springer International Publishing. [bib|
http]

The RCC8 language is a widely-studied formalism for describing topological arrangements of spatial regions. Two fundamental reasoning problems that are associated with RCC8 are the problems of satisfiability and realization. Given a qualitative constraint network (QCN) of RCC8 , the satisfiability problem is deciding whether it is possible to assign regions to the spatial variables of the QCN in such a way that all of its constraints are satisfied (solution). The realization problem is producing an actual spatial model that can serve as a solution. Researchers in RCC8 focus either on symbolically checking the satisfiability of a QCN or on presenting a method to realize (valuate) a satisfiable QCN. To the best of our knowledge, a combination of those two lines of research has not been considered in the literature in a unified and homogeneous approach, as the first line deals with native constraint-based methods, and the second one with rich mathematical structures that are difficult to implement. In this article, we combine the two aforementioned lines of research and explore the opportunities that surface by interrelating the corresponding reasoning problems, viz., the problems of satisfiability and realization. We restrict ourselves to QCNs that, when satisfiable, are realizable with rectangles. In particular, we propose an incremental SAT -based approach for providing a framework that reasons about the RCC8 language in a counterexample-guided manner. The incrementality of our approach also avoids the usual blow-up and the lack of scalability in SAT -based encodings. Specifically, our SAT -translation is parsimonious, i.e, constraints are added incrementally in a manner that guides the embedded SAT -solver and forbids it to find the same counter-example twice. We experimentally evaluated our approach and studied its scalability against state-of-the-art solvers for reasoning about RCC8 relations using a varied dataset of instances. The approach scales up and is competitive with the state of the art for the considered benchmarks.

Glorian, G., Boussemart, F., Lagniez, J.-M., Lecoutre, C., and Mazure, B. (2017b).
**Combining Nogoods in Restart-Based Search**, pages 129--138. Springer International Publishing,
Cham. [bib|
http]

Nogood recording is a form of learning that has been shown useful for solving constraint satisfaction problems. One simple approach involves recording nogoods that are extracted from the rightmost branches of the successive trees built by a backtrack search algorithm with restarts. In this paper, we propose several mechanisms to reason with so-called increasing-nogoods that exactly correspond to the states reached at the end of each search run. Interestingly, some similarities that can be observed between increasing-nogoods allow us to propose new original ways of dynamically combining them in order to improve the overall filtering capability of the learning system. Our preliminary results show the practical interest of our approach.

Glorian, G., Boussemart, F., Lagniez, J., Lecoutre, C., and Mazure,
B. (2017a). **Combinaison de nogoods extraits au redémarrage**. In *Treizièmes journées Francophones
de Programmation par Contraintes, JFPC 2017, Montreuil-sur-mer, France, 13 au 15 juin, 2017, Actes
*, volume 13, pages 55--64. AFPC. [bib]
Best student paper award

Dans cet article, nous nous intéressons à l’enregistrement de nogoods, instanciations partielles globalement incohérentes, pouvant être extraits systématiquement lors du redémarrage d’un algorithme complet (avec retour-arrière) de résolution CSP (problème de satisfaction de contraintes). Plus précisément, dans ce contexte, nous proposons plusieurs techniques de simplification et de combinaison de nogoods, dans le but d’accroître leur capacité de filtrage. La base de notre approche est une généralisation des nld-nogoods correspondant au concept introduit récemment d’increasing-nogoods. Nous proposons plusieurs algorithmes portant sur des combinaisons de sous-ensembles de nogoods identifiés de manière dynamique. Les similarités entre les différents increasing-nogoods permettent un meilleur élagage de l’arbre de recherche, notamment grâce à l’exploitation d’équivalences entre décisions. Nous proposons aussi quelques pistes d’amélioration, notamment un système de sentinelles et la génération de nld-nogoods à la volée. Nos résultats préliminaires montrent l’intérêt de notre approche pour certains problèmes.

NACRE
Gold medal on CSP
Minitrack of the 2018 XCSP3 Competition

NACRE is a constraint solver written in C++. The main purpose of this solver is to experiment nogood recording (with a clause reasoning engine) in Constraint Programming (CP). In particular, the data structures of the solver have been carefully designed to play around nogoods and clauses. This is the first version of the solver and it has been submitted to the XCSP3 2018 competition under the CSP MiniTrack.

Treizièmes journées Francophones de Programmation
par Contraintes - Montreuil sur Mer, France - JFPC'17

Journées des Doctorants (CRIL) - Le Touquet, France
- 2017

The 30th International Conference on Industrial,
Engineering, Other Applications of Applied Intelligent Systems - Arras, France - IEA/AIE
2017

The 24th International Conference on Principles and
Practice of Constraint Programming - Lille, France - CP'18

Networks (M1)

Advanced C Programming (L3)

Programming & Algorithm 5 (L3)

Programming & Algorithm 4 (L2)

Digital Culture (L1)

glorian [at] cril [dot] fr

Poste 15 80 71

03 21 79 17 70

CRIL-CNRS UMR8188

Université d'Artois

Faculté des Sciences Jean Perrin

Rue Jean Souvraz
SP 18

F-62307 LENS Cedex (France)

See on CRIL website