Optimisation et Recherche opérationnelle : quel algo ?

Salut à tous !

Je me tourne vers vous aujourd'hui, car je suis dans une impasse. Je dois réaliser un projet dans le cadre d'un cours intitulé "Optimisation et recherche opérationnelle".

Comme vous vous en doutez, nous étudions dans cette matière, différentes méthodes d'optimisation. Au programme, nous avons :

- programmation linéaire
- programmation en nombres entiers : méthode des coupes
- application des graphes à la Recherche Opérationnelle : programmation dynamique, recherche arborescente
- méthodes heuristiques : algorithme de descente et du kangourou, recuit simulé, méthode tabou.
- optimisation distribuée : colonie de fourmis, intelligence en essaim
- optimisation de processus stochastiques
- théories des jeux
- algorithme génétique

Pour le moment, nous n'en sommes qu'au premier point, c'est à dire la programmation linéaire. Cependant, les profs nous ont déja donné le sujet de notre projet, et pour cause, il est compliqué et long à réaliser. Nous pouvons utiliser la méthode que nous voulons, du moment que les résultats obtenus sont bons. Nous pouvons même utiliser une méthode qui n'est pas au programme du cours.

Je dois rendre la spécification de ce projet pour le 12 avril. Nous avons eu le sujet cette semaine, et je ne vois meme pas par où commencer...

Je vais quand meme vous parler du sujet :D

Il s'agit d'écrire un programme, dans le langage de notre choix, qui permettra de gérer les emplois du temps de notre école de meilleure façon qu'ils ne le sont actuellement. On fournira 2 fichiers texte au programme. Le premier contient la liste de tous les cours, TD et TP et les jours et horaire de leur plannification. Le second contient la liste des étudiants, et les unité de valeurs (cours) auxquelles il est inscrit.
Le programme devra calculer la meilleure façon de répartir les différents étudiants dans les différents cours, TD et TP, afin qu'il y ait le moins d'incompatibilité possible (2 TD en meme temps par exemple).

Vous pouvez voir le sujet détaillé du projet en suivant ce lien : www.ifrance.com/brigadenord/sujet.pdf

Mon problème est le suivant : je ne sais pas du tout quel algorithme utiliser pour gérer ce problème, étant donné que je n'en connais aucun. J'ai cherché sur internet, mais je ne trouve rien qui explique clairement le fonctionnement d'un des algorithme cité plus haut, et je dois connaitre le fonctionnement de tous, si je veux choisir le plus adapté...

Ma question : est-ce que quelqu'un pourrait me diriger vers un algorithme qu'il sait adapté à ce projet, ou m'expliquer le fonctionnement des algos cité plus haut ?

D'avance merci pour le coup de main.

Nicolas

C'est marrant, je reconnais bien là le style de l'UTBM:
- on te file tous les projets à la dernière minute, bien sûr tous en même temps, et la spécification "c'était pour hier" (si je ne me trompe pas, c'est en pleine période de partiels que tu dois la rendre?)

- comme ils sont incapables de résoudre les problèmes eux-mêmes, ils donnent cela comme sujet aux futurs ingénieurs que vous êtes

- mais où est le problème? la plupart des UV sont soit "obligatoires", soit "fortement conseillées" (ce qui revient au même en fait) donc au final, on n'a plus que le choix des UV de culture générale...

- qu'est-ce que ça change d'avoir un prix à la fin? le but c'est d'avoir le nombre d'UV suffisantes pour avoir le diplôme, pas d'avoir 18 dans l'une et en-dessous de la moyenne dans une autre... à moins que le "prix" soit en espèces sonnantes et trébuchantes (vu les budgets qu'ils ont chaque année, ils peuvent se le permettre!)

- au programme des cours, on vous file plein de noms d'algos, mais aucun n'est expliqué en profondeur. A vous de faire des recherches de votre coté. Au final, vous savez à peu près rien sur à peu près tout...

***
Maintenant, plus sérieusement, je ne connais pas tous les algos que tu cites, mais au niveau implémentation tu peux éventuellement te tourner vers le langage Prolog, qui est prévu pour résoudre ce genre de problèmes.

En effet, Prolog est très expressif et te permet d'exprimer de manière simple des relations, des contraintes, etc. Prolog est aussi doté d'un méchanisme de "retour arrière" (backtracking) qui te permet d'examiner une solution, de revenir en arrière si elle ne convient pas, avant d'examiner d'autres solutions éventuelles.

Contrairement à d'autres langages, tu ne passes pas le plus clair de ton temps à allouer/désallouer des objets en mémoire. En Prolog, on se concentre essentiellement sur la résolution du problème. Prolog a une syntaxe très concise.

Prolog est indépendant de la plateforme.

Prolog s'interface avec d'autres langages (C, Java). Tu peux notamment envisager de lire/écrire les fichiers avec un programme C mais d'avoir ton "moteur" de résolution en Prolog. Tu peux aussi essayer de tout faire en Prolog et donc de compiler ton programme Prolog.

***
Il s'agit là d'une piste pour t'aider à commencer ta recherche.

Ce que je te conseille de faire:
1) tu te documentes sur Prolog
2) tu installes un interprêteur Prolog (je te conseille swi-prolog, car gratuit et bien fait), tu t'inities un peu au langage
3) tu essayes de représenter ton problème sous forme de prédicats Prolog

Si tu arrives à représenter ton problème (données, contraintes) sous forme de prédicats Prolog, tu pourras envisager une résolution. Cela te donnera rapidement une idée du potentiel de ce langage (et constitue une bonne partie de ton travail de spécification).

Si tu décides de garder Prolog pour la résolution du problème, la question sera alors: "sous quelle forme rendre le projet?" (compiler un programme Prolog ou faire intéragir Prolog et un autre langage?). A voir en fonction du contexte.

Sache que j'ai eu une discussion avec un modérateur de DVP quant à la possibilité de resoudre des problèmes d'emploi du temps avec Prolog. Il apparait que c'est tout à fait possible et relativement simple à coder.

***
Pour ce qui est de la documentation sur le langage, je t'invite à jeter un oeil à mes articles sur le sujet:
http://pcaboche.developpez.com/

A venir: différents types de parcours de solutions (en profondeur, en largeur, avec heuristique...)

***
Voilà, je te souhaite bonne chance pour ton projet !

(et pardon pour la pub sur Prolog, ça doit bien faire la 3ème fois que je parle de ce langage dans la section "algorithmes" du forum. J'invite les modérateurs à me contacter en cas de problèmes. Je suis ouvert au dialogue)

Je ne connais pas encore Prolog, mais j'en ai entendu parlé de la meme manière que celle dont tu en parles. Le problème, c'est que je n'ai pas beaucoup de temps pour bien me mettre à prolog, et résoudre ce problème.

Par ailleurs, si je n'utilise pas un algo bete et méchant, ça risque de pas plaire aux profs, car le but de l'uv, c'est quand meme l'optimisation par algorithmes...

Sinon, je vois que tu connais bien le fonctionnement de l'utbm :roll:

Citation:

---

Envoyé par temar

Je ne connais pas encore Prolog, mais j'en ai entendu parlé de la meme manière que celle dont tu en parles.

---

C'est pas très compliqué en soi. La plupart du temps c'est juste assez mal enseigné et c'est pour cela que j'ai écrit des articles sur le sujet.

Si moi j'y arrive en Prolog, tu devrais logiquement y arriver aussi ! (t'es UTBMien en cycle ingénieur, non?).

Citation:

---

Envoyé par temar

Le problème, c'est que je n'ai pas beaucoup de temps pour bien me mettre à prolog, et résoudre ce problème.

---

C'est pour cela qu'on est là! Si t'as un problème en Prolog, il te suffit de poser ta question dans la section "autres langages".



Je pense honnêtement que la représentation de ton problème serait hyper simple en Prolog. T'aurais des prédicats du genre:

Code:

---

1 2 3 4 5 6

etudiant('Paul Machin'). etudiant('Patrick Bidulle'). etudiant('Isabelle Truc').   souhaiteUV('Patrick Bidulle', 'AG41'). ...

---

Tu pourrais mettre à jour les prédicats au moyens d'assert/retract (un peu comme dans une base de données), exprimer facilement des contraintes, etc. Franchement, en C++ par exemple, tu risques de faire beaucoup de "pissage de code" pour rien...

Essaye juste de représenter les données au moyen de prédicats Prolog et commence à réfléchir aux contraintes, le reste ça va tout seul !

Citation:

---

Envoyé par temar

Par ailleurs, si je n'utilise pas un algo bete et méchant, ça risque de pas plaire aux profs...

---

Pourquoi? Ils risquent de pas comprendre si l'algo est trop compliqué? :lol:
Plus sérieusement, tu peux aussi faire des algos betes et méchants en Prolog, tu sais!

Citation:

---

Envoyé par temar

Sinon, je vois que tu connais bien le fonctionnement de l'utbm :roll:

---

Malheureusement! :roll:
L'UTBM, j'étais content d'y rentrer mais encore plus content d'en sortir... Aujourd'hui je suis ingénieur issus de la fac et fier de l'être! (finalement, j'ai appris beaucoup plus de choses ailleurs)

Au fait, t'es sur le site de Belfort ou ils ont encore changé l'emplacement du département info?

Citation:

---

Envoyé par pcaboche

Si moi j'y arrive en Prolog, tu devrais logiquement y arriver aussi ! (t'es UTBMien en cycle ingénieur, non?).

---

Oui oui, j'y suis, mais 4 projets en meme temps (+ les exams qui débarquent bientôt), ça laisse pas beaucoup de temps pour apprendre un nouveau langage juste pour ce projet. Je demanderai quand meme au prof si le prolog ne le dérange pas :/

Citation:

---

Envoyé par pcaboche

Citation:

---

Envoyé par temar

Sinon, je vois que tu connais bien le fonctionnement de l'utbm :roll:

---

Malheureusement! :roll:
L'UTBM, j'étais content d'y rentrer mais encore plus content d'en sortir... Aujourd'hui je suis ingénieur issus de la fac et fier de l'être! (finalement, j'ai appris beaucoup plus de choses ailleurs)

---

Parti de ton plein gré ?

Citation:

---

Envoyé par pcaboche

Au fait, t'es sur le site de Belfort ou ils ont encore changé l'emplacement du département info?

---

Ouais ouais, on est toujours sur Belfort... Cte belle ville :marteau:


Enfin, bref, je me tournerai vers ta solution si je n'en ai pas d'autre. Merci pour les liens, je note ce que tu as fait sur prolog, j'en aurai besoin pour le cours d'intelligence artificielle ;-)

Citation:

---

Envoyé par temar

Oui oui, j'y suis, mais 4 projets en meme temps (+ les exams qui débarquent bientôt), ça laisse pas beaucoup de temps pour apprendre un nouveau langage juste pour ce projet.

---

Je sais ce que c'est :roll: (ne crois pas: avoir plein de projets en même temps n'est pas l'apanage de l'UTBM :wink: )

D'ailleurs les conseils que je te donne, c'est pas pour t'embrouiller, c'est au contraire pour essayer de te faire gagner du temps avec des solutions pas trop longues/difficiles à mettre en place.

Citation:

---

Envoyé par temar

Je demanderai quand meme au prof si le prolog ne le dérange pas :/

---

La réponse du prof risque d'être: "Prolog? Connais pas! Tu feras ton projet entièrement dans tel langage vu que c'est le seul que je connaisse..." (des fois tu te demandes si t'en connais pas plus qu'eux :koi: :aie: )

Citation:

---

Envoyé par temar

Parti de ton plein gré ?

---

Un peu des deux: j'étais nul en maths et l'école me gonflait. Du coup, quand j'ai été convoqué, je leur ai annoncé que je voulais me réorienter vers l'IUT. En IUT je me suis senti revivre. Je n'ai pas voulu réintégrer l'UTBM, jugeant que l'enseignement était trop pourri. J'ai fait une année en Angleterre et le reste en UFR ST (maîtrise pro). J'ai pas voulu faire recherche parce que je commençais à en avoir marre des études.

C'est à en UFR que j'ai découvert Prolog.

Citation:

---

Envoyé par temar

Ouais ouais, on est toujours sur Belfort... Cte belle ville :marteau:

---

Bof, il y a pire ailleurs ! C'est surtout les locaux qui sont un peu pourris... pareil pour l'enseignement !

Citation:

---

Envoyé par temar

Enfin, bref, je me tournerai vers ta solution si je n'en ai pas d'autre.

---

Mouaif... j'aurais plutôt dit l'inverse: essayer de voir ce qu'on peut faire en Prolog (car adapté au problème) et si ça ne marche pas faire du "pissage de code" en C++/Java/autre.

Si tu décides d'utiliser un autre langage, pour la gestion de tes données, tu peux éventuellement te tourner vers sqlite. Ainsi t'auras pas à gérer les objets en mémoire: tu mets tout dans une BDD sqlite et tu fais tes traitements au moyen de requêtes SQL. Vu que c'est un SGBD basé sur des fichiers, t'as rien à installer. C'est une suggestion.

Citation:

---

Envoyé par temar

Merci pour les liens, je note ce que tu as fait sur prolog, j'en aurai besoin pour le cours d'intelligence artificielle ;-)

---

Pas de problème. N'hésite pas à me faire part de tes commentaires (j'aime bien connaitre la réaction des lecteurs).

J'ai commencé à lire ton didacticiel sur prolog. Effectivement, je prendrai ma décision après :roll:

Par contre, je peux te certifier que le prof en question connait Prolog, étant donné qu'il a enseigné l'intelligence artificielle, et prolog est le langage utilisé.

Je vais donc finir mon dimanche sur du prolog, et demain, je demande au prof si ça lui pose un problème.

Par contre, si j'utilise prolog pour ce projet, je risque de devoir le coupler avec un autre langage (java) pour lire des fichiers en entrée, et en générer un en sortie. J'espère que c'est pas trop compliqué à faire :p

Sinon, un dernier point, le meilleur projet sera mis en place, et utilisé par l'administration, pour gérer les futurs emploi du temps. Autrement dit, faut que ce soit utilisable simplement. Ils veulent donc n'avoir a utiliser qu'un exécutable.
Prolog, il faut forcemment un interpreteur sous la main non ? Et si je couple avec java, ça se passe comment ?

Merci pour le coup de main. En fait, si le prof est ok, je pense me tourner vers ta solution, car elle me plait de plus en plus.

Je risque d'avoir besoin d'aide :oops:

Bon allez, je retourne lire ton didacticiel :wink:

Citation:

---

Envoyé par temar

Par contre, je peux te certifier que le prof en question connait Prolog, étant donné qu'il a enseigné l'intelligence artificielle, et prolog est le langage utilisé.

---

Nickel !

Citation:

---

Envoyé par temar

Par contre, si j'utilise prolog pour ce projet, je risque de devoir le coupler avec un autre langage (java) pour lire des fichiers en entrée, et en générer un en sortie. J'espère que c'est pas trop compliqué à faire :p

---

Ca ne pose aucun problème au niveau programmation. On avait eu un projet en Java/Sicstus Prolog et ça s'est bien passé.

Pour l'intéropérabilité Java/Prolog, ça dépend de ton implémentation:
- swi-prolog: JPL (http://www.swi-prolog.org/packages/jpl/)
- Sicstus: Jasper
(Il y a un sujet là dessus dans la section "Autres langages")

Citation:

---

Envoyé par temar

Prolog, il faut forcemment un interpreteur sous la main non ? Et si je couple avec java, ça se passe comment ?

---

Je ne me souviens plus des détails techniques. Pour l'installation de JPL, c'est là:
http://www.swi-prolog.org/packages/j...tallation.html

Sinon, demande à ton prof, il pourra te renseigner (et te dire si il est d'accord)

Pour écrire un article sur l'intéropérabilité entre Prolog et d'autres langages, il me faudrait faire quelques recherches avant... et j'ai d'autres projets d'articles d'ici là !

Citation:

---

Envoyé par temar

Merci pour le coup de main. En fait, si le prof est ok, je pense me tourner vers ta solution, car elle me plait de plus en plus.

---

Cool :ccool:

Citation:

---

Envoyé par temar

Je risque d'avoir besoin d'aide :oops:

---

Pas de pb :arrow: rubrique "Autres langages" (et envoie-moi un mp, parce que je vais aussi sur d'autres sections du forum)

Citation:

---

Envoyé par temar

Bon allez, je retourne lire ton didacticiel :wink:

---

Bonne lecture !

un des problèmes important sur ce projet, c'est le temps !!!


en fait il faut que ce soit très rapide et surtout que ca puisse donner une solution à un moment donné par le prof.

hors, si je ne me trompe pas ... il n'y a pas de solution intermédiaire avec la programmation par contraintes?

donc on risque de n'avoir aucune solution à donner à un moment précis ?

si on opte pour une solution, on met n'importe quelle UV de la personne à un emplacement libre, puis quand on bloque on fait du backtraking pour modifier.. mais à un moment donné on a une solution (meme si y'a un conflit)

je me fais comprendre ?