Diplômés 2019

Le 10 septembre 2019, trois étudiants du parcours recherche ont soutenu leur mémoire de fin d'études. Félicitations à eux !

• Approches par partitionnement et par portfolio en programmation par contraintes, Samvel Dersarkissian
• Factorization of Discrete Dynamical Systems and Computational Complexity, Sara Riva
• Maintenance and Flight Scheduling, Pierre Tassel

Approches par partitionnement et par portfolio en programmation par contraintes, Samvel Dersarkissian

Tutor: Arnaud Malapert, Université Côte d’Azur, CNRS, I3S, France.

La programmation par contrainte (PPC) est une technique efficace permettant de résoudre des problèmes combinatoires complèxes. En PPC un problème est défini par un ensemble de variable, leurs domaines de définition et un ensemble de contraintes sur ces domaines. La résolution de ces problèmes se fait en deux étapes : la première supprime les valeurs des variables qui sont incompatibles avec les contraintes, et la seconde cherche une instanciation des variables qui résout le problème. Embarrassingly Parallel Search (EPS) est une méthode qui permet de paralléliser la résolution de tels problèmes. Bien que la méthode en elle-même soit générique, ses implémentations actuelles dépendent des architectures des machines pour lesquelles elles ont été programmées ce qui limite fortement leur utilisation en pratique. Nous proposons de revoir le fonctionnement des communications au sein d’EPS de sorte à la rendre plus facilement utilisable sur une ou plusieurs machines quelconques. Nos exposons ensuite l’implémentation d’un prototype et d’une maquette de solveur permettant de tester les limites de ce prototype.

Constraint programming (CP) is an effective technique for solving complex combinatorial problems. In CP a problem is defined by a set of variables, their domains and a set of constraints on these domains. The resolution of these problems is done in two steps: the first one deletes the values of the variables that are incompatible with the constraints, and the second one looks for an instantiation of the variables that solves the problem. Embarrassingly Parallel Search (EPS) is a method of parallelizing the resolution of such problems. Although the method itself is generic, its current implementations depend on the architectures of the machines for which they have been programmed, which severely limits their use in practice. We propose to review the functioning of communications within EPS so that it can be more easily used on any and/or multiple machines. We then present the implementation of a prototype and a mockup solver to test the limits of this prototype.

Samvel is now a PhD student at the I3S laboratory.

Factorization of Discrete Dynamical Systems and Computational Complexity, Sara Riva

Tutor: Enrico Formenti, Université Côte d’Azur, CNRS, I3S, France.

Boolean automata networks, genetic regulation networks, and metabolic networks are just a few examples of biological modeling by discrete dynamical systems (DDS). All these real phenomena, once modeled as DDS, present complex dynamics. In general, the model or hypotheses validation on these phenomena is difficult, also taking into account the uncertainty in the original experimental results. Using polynomial equations over discrete dynamical systems, it is possible to model the hypotheses on a system or to study simplifications of a certain dynamic. But to do this, it is necessary to solve these equations, a problem in general undecidable. So we try to solve a first abstraction of the problem, i.e. equations that model only hypotheses on the cyclic behavior of a system. We introduce a new notation that models how sum and product operations affect this cyclical behavior. We show that many equations can be solved, being reduced to simpler cases. Finally, we present two algorithms: the colored-tree and the SAT-Based. Our experimental analysis indicate that we are now able to verify hypotheses on DDS of reasonable size.

Sara is now a PhD student at the I3S laboratory.

Maintenance and Flight Scheduling, Pierre Tassel

Tutor: Mohamed Rbaia, Amadeus, Sophia Antipolis, France.
Jean-Charles Régin, Université Côte d’Azur, Inria, CNRS, I3S, France.

In order to be operational, federal aviation regulation requires all aircraft to perform certain types of maintenance after a certain number of hours of fly, take off/landing or days since the last maintenance. Given the original planning, the algorithm presented in this report allocates the maintenance to each aircraft of a given fleet while respecting certain maintenance criteria and without creating violations in the planning. This algorithm was tested on 4 different instances, focusing on 4 different types of maintenance (one cyclic and the other ones depending on flying hours or landing/take off counters) on the international fleet and has been able to allocate all maintenance without creating violations.

Pierre is now a PhD student at Universität Klagenfurt.