Recherche opérationnelle

Description : Le cours est une introduction aux problèmes d’optimisation combinatoire dans le cadre appliqué de la recherche opérationnelle. Cette dernière recouvre les méthodes d’optimisation formelles utiles aux organisations (entreprises, etc) pour prendre des décisions rationnelles, que ce soit en logistique, en stratégie (plans d’investissement, etc), en économie, etc. Ce cours et celui d’optimisation sont deux cours indissociables au sens où ils se répartissent la présentation des différentes techniques d’optimisation, selon la nature des problèmes que ces techniques résolvent : quand le cours d’optimisation se concentre sur les méthodes d’analyse numérique optimisant une fonction continue définie dans un espace euclidien, RECHOP aborde les problèmes d’optimisation combinatoire dans un espace discret dont la résolution est davantage algorithmique. De ce fait, ce cours fait une large place aux algorithmes et à leur complexité et peut à ce titre vu comme le prolongement du cours de 1ère année “Structures de données et algorithmes” (SDA). Le cours commencera par aborder les problèmes combinatoires dans le cadre très général de la programmation par contraintes. On se concentrera ensuite sur des instances de problèmes pour lesquels une résolution en temps polynomial existe, comme la programmaiton dynamique ou les problèmes de couplages de graphes. On développera également des algorithmes d’approximation efficaces pour le problème difficile de la programmation linéaire entière après que la programmation linéaire a été traitée en cours d’optimisation, faisant ainsi le lien entre les deux cours.

Acquis d’apprentissage : A l’issue de ce cours, les élèves auront une culture générale sur le type de problèmes rencontrés en recherche opérationnelle. Ils sauront formaliser un besoin en recherche opérationnelle et reconnaitre la nature précise du problème combinatoire sous-jacent. Le cas échéant, ils sauront associer à ce problème combinatoire une technique de résolution adaptée.

Modalités d’évaluation : Examen écrit 1h30, rattrapable

Compétences évaluées :

Modélisation
Recherche et Développement

Responsable de cours : Nicolas Jozefowiez

Identifiant Geode : SPM-INF-013

CM :

Programmation par contraintes (1.5 h)
Problèmes d’optimisation temporelle. Programmation dynamique (1.5 h)
Problème d’affectations: couplage de graphes et mariages stables (1.5 h)
Programmation linéaire entière (1.5 h)

TP :

Programmation par contraintes (3.0 h)
Programmation dynamique (3.0 h)
Problèmes de couplage (3.0 h)
Programmation linéaire entière (3.0 h)