enseignements

sophie demassey

xkcd

précédemment

Advanced Integer Linear Programming (2009-2012)

Cours magistral en anglais, niveau M2. Principales sources: Integer Programming, L. Wolsey et l'excellent Jeff Linderoth's course at Lehigh University.

lectures and course notes

lec 1-3
Modeling (slides) modeling combinatorial elements, logical conditions, numerical conditions and non-linear value functions; strong and ideal models; strengthening models; special ordered sets, total unimodularity, aggregated/disaggregated models, compact/decomposed models.
lec 4
Applications (exercices) models of packing, scheduling, transportation, graphs.
lec 5-6
Solving (slides) cutting-planes, branch-and-bound; template paradigm, generic and specific cuts: MIR, clique, cover, odd-cycle, subtour elimination; branching and node selection strategies: variable, GUB and SOS dichotomy, strong branching, DFS/BFS.
lec 7-8
Relaxations (notes) combinatorial, dual, LP, surrogate and lagrangian relaxations; applications to the Multi-Knapsack Problem; strength of the lagrangian dual, solving by cutting-planes or subgradient algorithms; lagrangian-based heuristics, variable fixing, branching strategies.
lec 9
Decompositions (slides) LP-based decompositions: cutting-plane method, lagrangian relaxation, lagrangian decomposition, Benders decomposition, Dantzig-Wolfe decomposition; column generation, primal-dual interpretations, branch-and-price.

examinations

APP de Recherche Opérationnelle (2008-2012)

Cours en trois volets sur les applications des techniques avancées de RO, niveau M2. Méthode pédagogique inspirée de l'Apprentissage par Projet et par la Pratique: travail en groupe, découverte et/ou approfondissement d'une technique autour d'une application.

APP 1
Optimisation dans les graphes et le transport (cahier d'exercices): flots et couplage, couverture, clique et partition, TSP, VRPTW; complexité; algorithmes de graphe; modèles de PLNE, dualité, relaxation continue, génération de coupes; algorithmes constructifs, recherche locale, algorithmes d'approximation.
APP 2
Optimisation pour l'allocation et le placement (cahier d'exercices): knapsack, multi-knapsack, bin-packing, cutting-stock; complexité; programmation dynamique; modèles de PLNE, relaxations continue, surrogate, lagrangienne, décomposition DW, génération de colonnes; algorithmes constructifs.
APP 3
Note de cours: brève introduction à la classification des problèmes d'ordonnancement.

examens

Séries Génératrices (2011-2012)

Cours magistral de Mathématiques pour l'informatique axé sur les séquences d'entiers et les séries génératrices appliquées à la récursion, au dénombrement et à la complexité, niveau L3.

documents de cours

cours
(transparents) suites d'entiers; séries génératrices et résolution de récurrences; exemples et applications.
TD 1
Preuve par récurrence (exercices corrigés) récurrence simple, généralisée, multiple.
TD 2
Applications (exercices corrigés) calcul de complexité et dénombrement.
aide-mémoire
(notes)
examen 2011
(questions+solutions)

Programmation par Contraintes (2005-2012)

Activité pratique en deux volets, niveau M2. Chaque activité est construite autour d'une problématique à résoudre par PPC au moyen de la librairie Choco et organisée en 3 séances de TD et un développement individuel entre chaque séance à partir d'un code à trou Java/Choco fourni.

documents de cours

projet 1
Nurse Scheduling Problem (cahier d'exercices et code à trou) modèles de conditions logiques, contraintes globales et agrégation de contraintes, contraintes automates, symmétries, utilisation de stratégies de branchement.
projet 2
Traveling Salesman Problem with Time Windows (cahier d'exercices) filtrage de la contrainte d'élimination de sous-tours; développement d'une contrainte globale, développement d'une stratégie de branchement.
séminaire
Hybridations PPC/RO (slides)

Espace Intégrateur: partie Informatique (2007-2009)

Activité pratique multi-disciplinaire en deux volets, niveau L2. Chaque activité est construite autour de l'étude d'un système dynamique physique, conduite à la fois de manière expérimentale (TP de physique) et analytique (TD de mathématiques). Ces deux études sont alors intégrées dans un logiciel de simulation/visualisation développé individuellement en Java/JFreeChart à partir d'un code à trou fourni. Il s'agit de développer un outil de calcul des solutions théoriques, et de tracé des solutions théoriques et des relevés expérimentaux.

documents de cours

projet 1
Lève-charge (cahier d'exercices 2007, cahier d'exercices 2008 et code source solution) trajectoire d'une masse suspendue à un système élastique de lève-charge.
projet 2
Température (cahier d'exercices 2007) évolution temporelle de la température d'une plaque au cours de sa trempe.

Projets algorithmique et programmation (2002-2012)

Sujets libres de programmation, niveau L2.

sujets