Stages sur la programmation par contraintes (PPC)
14/12/10 10:30 |
Stages 2010/11
Laboratoire : I3S, Sophia Antipolis
Equipe : CeP
Contact : Jean-Charles Régin (jean-charles point regin arobase unice point fr)
Les étudiants seront amenés à utiliser des solvers basés sur la PPC dejà existant
Equipe : CeP
Contact : Jean-Charles Régin (jean-charles point regin arobase unice point fr)
L'équipe CeP propose les stages suivants tous basés
sur la programmation par contraintes (PPC).
Remarque : il n'est pas nécessaire de connaitre la
programmation par contraintes. L'idée de base de la
PPC est de résoudre des problèmes complexes de
facon exacte en utilisant la résolution de
sous-problèmes (contraintes) faciles inclus dans le
problème général.
Les étudiants seront amenés à utiliser des solvers basés sur la PPC dejà existant
Sujets :
1) PPC et multithreading : il s'agit d'écrire le code permettant de lancer des solver en parallèle sur une machine multicoeurs.
2) Combinaisons de contraintes : il s'agit d'énumérer les solutions de 2 contraintes puis de les combiner sous la forme d'une seule contrainte plus générale et d'étudier les performances de la combinaison obtenue. L'étudiant devra coder.
3) Recherche de toutes les solutions dans un problème de PPC. Lors de l'énumération de toutes les solutions, l'utilisateur fait face à un grand nombre de symmétries. Il s'agit d'essayer de limiter l'explosition combinatoire (par exemple si 2 variables x et y peut prendre les memes valeurs alors on essaiera de ne produire que les solutions ou x <= y). L'étudiant pourra coder mais ce n'est pas obligatoire.
4) Application des heuristiques de l'algorithme de Belmann-Ford dans le cadre de la PPC. Il s'agit ici principalement de coder les heuristiques de Bellmann-Ford en PPC. L'étudiant devra être imaginatif pour résoudre certains problèmes
5) Affichage de données liées à la PPC et notamment au problème du bin-packing. L'étudiant devra définir une interface graphique claire et la programmer pour afficher des résolutions de problèmes dit de bin-packing.
1) PPC et multithreading : il s'agit d'écrire le code permettant de lancer des solver en parallèle sur une machine multicoeurs.
2) Combinaisons de contraintes : il s'agit d'énumérer les solutions de 2 contraintes puis de les combiner sous la forme d'une seule contrainte plus générale et d'étudier les performances de la combinaison obtenue. L'étudiant devra coder.
3) Recherche de toutes les solutions dans un problème de PPC. Lors de l'énumération de toutes les solutions, l'utilisateur fait face à un grand nombre de symmétries. Il s'agit d'essayer de limiter l'explosition combinatoire (par exemple si 2 variables x et y peut prendre les memes valeurs alors on essaiera de ne produire que les solutions ou x <= y). L'étudiant pourra coder mais ce n'est pas obligatoire.
4) Application des heuristiques de l'algorithme de Belmann-Ford dans le cadre de la PPC. Il s'agit ici principalement de coder les heuristiques de Bellmann-Ford en PPC. L'étudiant devra être imaginatif pour résoudre certains problèmes
5) Affichage de données liées à la PPC et notamment au problème du bin-packing. L'étudiant devra définir une interface graphique claire et la programmer pour afficher des résolutions de problèmes dit de bin-packing.