Clément Legrand

Student at the ENS Rennes in computer science

More about me?


Learnheuristic for CVRP

Project realised during an internship from May to July 2018, in the team ORKAD at CRIStAL laboratory of Lille.
Many algorithms are created to solve combinatorial optimisation problem, or improve existing solutions. The Capacitated Vehicle Routing Problem is such a problem. In most problems, we can extract some knowledge from small instances. Then integrate this knowledge in an algorithm can create a learning heuristic, that improves the initial algorithm. My purpose was to create such an heuristic.
All details are given in the following paper (in french) : Report_L3 .

A solver for the generalized rush hour.

A small project realised during my first-year of Master, in 2018.
The article details the construction of a solver for a PSPACE-complete problem: Generalized Rush Hour. See the article for more details: Article_rush-hour

About the prediction of good edges for the CVRP and its applications.

Project realised during my Master's Internship (first-year) in collaboration with Daniele Vigo and Luca Acorsi at Bologna, in Italy.
Few decades ago, it was almost impossible to solve with high precision large combinatorial optimization problems. Due to their exponential solution space, even now with all computers of the world, small instances cannot be optimally solved with a naive approach. To solve CVRP instances, the idea is to use machine learning to predict good edges that can appear in optimal solutions. For more details, see the article: Report_M1

Combinatorial methods, enumeration problems

A memory realised during my preparation for the aggregation in 2020.
The manuscript details common methods use to solve some enumeration problems. An online version is available here (in french): Math_memory