C'est quoi comme école ?
Tu as eu des cours de recherches opérationnelle dans ton cursus ? Si oui as-tu entendu parlé de méta heuristique, de recherche locale, de simplexe, ou de branch & bound ?
Pour ce qui est des solveurs : as-tu déjà entendu parler de cplex ou de coin ?
Concrètement c'est un sujet de stage ou un projet donné par un de tes profs ?
Concrètement il faut :
1) définir par écrit ce qu'on cherche (variables), ce qu'on aimerait idéalement (objectif), ce qu'on ne veut pas (contraintes).
2) transformer chacunes des contraintes et l'objectif sous forme d'expression mathématique (inéquations, inéquations, contraintes de domaine,...). De manière générale il faut essayer d'avoir un seul objectif (le critère qu'on va optimiser), des contraintes ayant une "bonne tête" (par exemple préférer des contraintes linéaires à des contraintes quadratiques). Les méthodes approchées servent en particulier quand un problème est trop difficile à résoudre à l'exact. Tu auras alors défini ce fameux modèle mathématique.
3) Ensuite il faut te demander si tu veux la (une) solution optimale (résolution exacte) ou si tu peux te contenter d'une résolution approchée. Le choix de la méthode de résolution dépend fortement de la taille du problème, de la forme des contraintes etc...
a- Une résolution exacte est généralement plus longue (Branch & bound + simplexes) et nécessitent à priori un solveur comme coin ou cplex. Dans ce genre de modélisation on a intérêt à utiliser dans la mesure du possible des variables continues et des contraintes linéaires. Cf simplexe, branch and bound, branch and cut...
b- Une résolution approchée est plus rapide mais reste approchée et on ne connaît pas forcément le gap entre la solution trouvée et la solution optimale. C'est en général assez simple à programmer (cf meta heuristiques, recherche tabou par exemple). Ces approches sont particulièrement adaptées quand on a beaucoup de variables discrètes (variables entières par exemple) bornées (par exemple {0,1,2,3}. A noter que dans cette approche on peut aisément manipuler des variables discrète non numériques. Cf par exemple un tutoriel sur les CSP et les métaheuristiques...
Bonne chance
"emploi du temps" gantt
