Offre de stage Master 2 : Sélection et combinaison d’algorithmes sous contraintes de ressources

16 oct. 2024

Description de l’offre : lien url

Information pratiques:

Context

Constraint Programming (CP) is a field of Artificial Intelligence that aims to propose mathematical modeling languages allowing to express combinatorial problems and offering generic algorithms to solve them. Two open-source solvers, choco [6] in Java and toulbar2 [2] in C++, integrate a collection of algorithms collected for more than twenty years. The command line of toulbar2 contains about fifty parameters and there are many other internal settings controlling the preprocessing of instances, the search algorithms, and their heuristics. The same goes for the choco solver. Improving the performance of these solvers by better tuning them is an important key to reducing their energy consumption and their potential embeddability (e.g., Android apps). The TASC team pursues theoretical and applied research in CP that it integrates into the choco solver (https: //choco-solver.org/). The SaAB team conducts work in combinatorial optimization in the life sciences and de- velops the toulbar2 solver (https://miat.inrae.fr/toulbar2). Both solvers have won several competitions in CP (https://xcsp.org/competitions, https://www.minizinc.org/challenge). In each competition, computing resources are limited in time and space.

Subject

The objective of the internship is to study new strategies for selecting and combining algorithms capable of processing very heterogeneous sets of instances while respecting the limits imposed on computation time and memory. Current algorithm selection techniques [3] come up against the time cost of evaluating a given strategy on a training set. One avenue to explore will be to extract one or more informative subproblems from the set of instances to speed up their evaluation. Different extraction techniques will be considered, including tree decomposition. Another promising area is evolutionary algorithms which aim to provide a general framework for modifying the code of an existing program by a process inspired by genetic algorithms [5, 4, 1]. The internship will begin by identifying the available algorithms, their theoretical and practical complexities (via profiling) to define the elementary bricks on which to test an evolutionary process aiming at selecting and controlling a combination of algorithms adapted to the target instances. The originality of the approach will be to take into account in this controller the limits imposed in time and space. The internship will also benefit from the Toulouse Research Institute in Natural and Artificial Intelligence (ANITI) within the industrial chair Heroic. Possibility of continuing with a PhD thesis (localized in Nantes) within the ANR GMLaS project (2025-2029) which focuses on improving combinatorial optimization techniques using data mining and machine learning.

To apply: Send your application file (CV, bachelor’s and master’s grades, cover letter) by email to the three supervisors before February 28, 2024.

References

[1] Robert Andrew Bennetto. Evolutionary search strategies in constraint programming. PhD thesis, Stellenbosch University, 2020.

[2] B Hurley, B O’Sullivan, D Allouche, G Katsirelos, T Schiex, M Zytnicki, and S de Givry. Multi-Language Evaluation of Exact Solvers in Graphical Model Discrete Optimization. Constraints, 21(3):413–434, 2016.

[3] Pascal Kerschke, Holger H Hoos, Frank Neumann, and Heike Trautmann. Automated algorithm selection: Survey and perspectives. Evolutionary computation, 27(1):3–45, 2019.

[4] Su Nguyen, Dhananjay Thiruvady, Mengjie Zhang, and Kay Chen Tan. A genetic programming approach for evolving variable selectors in constraint programming. IEEE Transactions on Evolutionary Computation, 25(3):492–507, 2021.

[5] Justyna Petke, William B. Langdon, and Mark Harman. Applying genetic improvement to minisat. In Günther Ruhe and Yuanyuan Zhang, editors, Search Based Software Engineering, pages 257–262, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.

[6] Charles Prud’homme and Jean-Guillaume Fages. Choco-solver: A java library for constraint programming. Journal of Open Source Software, 7(78):4708, 2022


Stage Master