Optimisation combinatoire

SAE optimisation

Ce projet porte sur la résolution du problème de l'anneau-étoile, un problème d'optimisation où il faut sélectionner des stations, affecter des points à ces stations, puis relier les stations retenues par un cycle. L'idée a été de comparer plusieurs stratégies de résolution dans un même dépôt Julia.

Voir le GitHub Me contacter

Vue d'ensemble

Le dépôt a été construit comme un terrain d'expérimentation autour d'un même problème combinatoire. Le code permet d'exécuter plusieurs méthodes sur des instances de référence, puis d'observer les résultats dans le terminal et dans des sorties graphiques générées par le projet.

Julia
JuMP
HiGHS
Plots

Ce que le projet montre

Capacité à formaliser un problème mathématique et à le traduire en code.
Comparaison entre méthodes approchées et méthode exacte sur un même sujet.
Prise en main d'un environnement Julia orienté optimisation.
Production d'un rapport liant théorie, choix algorithmiques et résultats observés.

Points techniques

Lecture d'instances `.tsp` avec différents jeux de données fournis.
Utilisation de `JuMP` et `HiGHS` pour la résolution exacte.
Implémentation séparée des stratégies heuristiques et métaheuristiques.
Scripts de lancement simplifiés via `make` pour accélérer les essais.
Export des résultats sous forme d'images dans le dossier du projet.

Lancer le projet

Le dépôt prévoit un usage sur machine personnelle ou sur les machines de l'université. Le plus simple est d'utiliser les cibles `make` fournies.

make run
make run_custom FILE=data/berlin52.tsp P=3 ALPHA=1

Sur l'environnement de la faculté, il existe aussi des commandes dédiées comme `make install_fac`, `make run_fac` et `make clean_fac`.