Gaël Glorian

Phd. Student at CRIL
Algorithms for Inference and Constraints


Distributed Optimization for combinatorial problems with large constraints supervised by Frédéric Boussemart, Jean-Marie Lagniez, Christophe Lecoutre and Bertrand Mazure

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

Research

Publications

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| DOI| 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.



Organizing Committee

Treizièmes journées Francophones de Programmation par Contraintes - Montreuil sur Mer - JFPC'17
Journées des Doctorants (CRIL) - Le Touquet - 2017
The 30th International Conference on Industrial, Engineering, Other Applications of Applied Intelligent Systems - Arras - IEA/AIE 2017


Teaching at Faculté des Sciences Jean Perrin

Réseaux (M1)
Algorithmique et programmation 5 (L3)
Algorithmique et programmation 4 (L2)
Culture numérique (L1)


Contact

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