programmation par contrainte

bonjour,
jai a programmer un empoi de temps dune ecole (primaire-complementaire) de 25 classes et plusieurs profs (cadres et contractuels) en principe en java.cest en fait mon sujet de memoire. dapres plusieurs recherches, jai choisi la librairie choco car elle est gratuite. mais je ne sais pas si elle peut me resoudre mon probleme ou si mon probleme sera resolu en programmation par contrainte car il y a trop de preferences.
est ce que quelqu'un peut m'aiguiller?
est ce que je dois continuer en programmation par contrainte ou dois-je me tourner vers la programmation genetique
je me suis perdue et jai pas trop de temps.
si qlq pourra m'aider

Salut,
Sans vouloir faire de pub, tu as fait un excellent choix 8-). Choco devrait être tout à fait capable de résoudre un problème d'emploi du temps.
Cependant garde bien en tête que l'efficacité de la programmation par contraintes dépends beaucoup de la modélisation.

Concernant les préférences, la plupart des problèmes d'emploi du temps sont infaisables si les préférences sont des contraintes dures. La solution la plus répandue consiste à en relâcher certaines et à maximiser/minimiser un objectif dépendant des préférences relâchées.
Normalement, vu la taille de ton problème, Cela devrait marcher avec un temps d'exécution correcte.

Bien sûr, tu peux aussi utiliser des métaheuristiques, mais dans le cadre d'un projet celà me semble plus intéressant d'apprendre à utiliser un solveur. N'hésite pas à poser des questions sur ce forum ou sur le forum de choco pour avoir de l'aide. Cherche des références sur les problèmes d'affectation en PPC pour t'en inspirer dans ta modélisation.

bonne chance.
N'hésite pas à laisser d'autres messages, ton problème est intéressant.

grand merci pour ta reponse. je voulais changer de sujet car je n'etais pas sure que cest un bon choix. maintenant tu me donne un elan. merci

mais est ce que tu peux me specifier les metaheuristiques et le solveur?
car suite a une recheche , jai choisi choco et non suite a une grande experience.
merci d'avance

Salut,
Je ne suis pas un spécialiste des problèmes d'emploi du temps. Ne prends donc pas toutes mes réponses au pied de la lettre.
Je pense que un algorithme de recherche local style Recherche tabu ou recuit simulé sera plus approprié qu'un algorithme génétique.
Pour le solveur, si tu ne peux pas te payer une licence ILOG solver, choco fera très bien l'affaire vu la taille de ton problème.
Si ton problème est sur-contraint et qu'il n'existe pas de solutions, la PPC n'en trouvera pas :lol:
Cependant, tu seras au courant que ton problème n'est pas satisfiable alors qu'une métaheuristique se contentera de chercher une solution satisfiable jusqu'à ce qu'elle dépasse une limite (temps ou nb itérations).
Si tu utilises la PPC et que ton problème est surcontraint, tu peux relacher des contraintes et les intégrer dans une fonction objectif. C'est la méthode la plus simple mais pas forcement la plus efficace car tu n'es pas sur de relacher les bonnes contraintes, i.e., celles qui font que ton problème n'a pas de solutions.

cette article résouds un problème d'emploi du temps complexe en utilisant la PPC. Il est résolu en utilisant PALM, une extension de choco.
La méthode proposée est complexe mais c'est pour te donner une idée. Tu n'es pas obligé d'utiliser les explications même si elles sont vraiment utiles dans ce genre de problème.

Si tu précises un peu les dimensions et les contraintes de ton problème, On aura une meilleure idée des techniques à utiliser.
Dans tous les cas, si tu veux utiliser la PPC, regarde de ces côtés là : explications, soft constraints.

Bonjour, je voulais juste faire part de mon expérience, ayant déjà créer une petite appli de génération d'EDT dans le cadre d'un projet scolaire. Il faut un minimum de connaissance en optimisation (recuit simulé, recherche tabou et heuristique) pour choisir la/les bonne(s) méthode(s) de recherche. J'ai personnellement choisi d'utiliser l'heuristique pour résoudre ce problème, et ce n'était pas spécialement la meilleur solution, bien que les résultats ne soient pas désagréables.

Quoi qu'il en soit, le problème n'est pas simple, et comme déjà indiqué ci-dessus, la modélisation est très importante pour obtenir quelque chose de cohérent.
Bon courage

Citation:

---

Envoyé par nono_31

Salut,
Sans vouloir faire de pub, tu as fait un excellent choix 8-). Choco devrait être tout à fait capable de résoudre un problème d'emploi du temps.
Cependant garde bien en tête que l'efficacité de la programmation par contraintes dépends beaucoup de la modélisation.

Concernant les préférences, la plupart des problèmes d'emploi du temps sont infaisables si les préférences sont des contraintes dures. La solution la plus répandue consiste à en relâcher certaines et à maximiser/minimiser un objectif dépendant des préférences relâchées.
Normalement, vu la taille de ton problème, Cela devrait marcher avec un temps d'exécution correcte.

Bien sûr, tu peux aussi utiliser des métaheuristiques, mais dans le cadre d'un projet celà me semble plus intéressant d'apprendre à utiliser un solveur. N'hésite pas à poser des questions sur ce forum ou sur le forum de choco pour avoir de l'aide. Cherche des références sur les problèmes d'affectation en PPC pour t'en inspirer dans ta modélisation.

bonne chance.
N'hésite pas à laisser d'autres messages, ton problème est intéressant.

---

bonjour , apres 8ans je fais le meme sujet , et je suis coincée , est çe qu'il faut choisir soit un solveur soit une methode ?
pourquoi