Recherche opérationnelle

Operations research

Description: The course is an introduction to combinatorial optimization problems in the applied context of operations research. The latter covers formal optimization methods useful to organizations (companies, etc.) for making rational decisions, whether in logistics, strategy (investment plans, etc.), economics, etc. This course and the optimization course are inseparable in the sense that they divide up the presentation of the various optimization techniques between them, depending on the nature of the problems these techniques solve: while the optimization course focuses on numerical analysis methods that optimize a continuous function defined in a Euclidean space, RECHOP addresses combinatorial optimization problems in a discrete space, the solution of which is more algorithmic. As a result, this course places a strong emphasis on algorithms and their complexity and can therefore be seen as an extension of the first-year course “Data Structures and Algorithms” (DSA). The course will begin by addressing combinatorial problems within the very general framework of constraint programming. We will then focus on instances of problems for which a polynomial-time solution exists, such as dynamic programming or graph matching problems. We will also develop efficient approximation algorithms for the difficult problem of integer linear programming after linear programming has been covered in the optimization course, thus linking the two courses.

Learning outcomes: At the end of this course, students will have a general understanding of the types of problems encountered in operational research. They will be able to formalize an operational research requirement and recognize the precise nature of the underlying combinatorial problem. Where appropriate, they will be able to match this combinatorial problem with a suitable solution technique.

Evaluation methods: 1h30 written test, can be retaken

Evaluated skills:

  • Modelling
  • Research and Development

Course supervisor: Nicolas Jozefowiez

Geode ID: SPM-INF-013

CM:

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

TP:

  1. Programmation par contraintes (3.0 h)
  2. Programmation dynamique (3.0 h)
  3. Problèmes de couplage (3.0 h)
  4. Programmation linéaire entière (3.0 h)