Préparer les étudiants à aborder les problèmes d'optimisation discrète que l'on rencontre dans de nombreux domaines d'applications. Les différentes phases d'un projet seront examinées : formulation du problème, construction d'un modèle mathématique, résolution du modèle et mise en œuvre informatique, étude de la solution obtenue. On introduira également les méthodes dites polyédriques qui fournissent un cadre assez général fondé sur la recherche d'inégalités valides pour la résolution de problèmes d'optimisation combinatoire. Cette méthodologie a été à l'origine de progrès importants réalisés sur le traitement de problèmes fondamentaux comme celui du Voyageur de commerce. L'objectif du cours est de faire comprendre les caractéristiques de l'approche, de présenter les descriptions polyédriques complètes de certains problèmes et les principales méthodes de recherche d'inégalités valides, et de montrer à travers certains problèmes phares l'efficacité de ces méthodes.
Expérience du responsable dans le domaine de l’UE
Enseignant en recherche opérationnelle (IIE-CNAM et Master STIC, spécialité MOCS)
Responsable de l’équipe de recherche “Optimisation combinatoire” du laboratoire CEDRIC
Co-Rédacteur en chef de la revue RAIRO-Operations Research
Responsable de la section d'enseignement Mathématiques et méthodes quantitatives à l'Institut d'Informatique d'Entreprise du CNAM et de l'option Optimisation de 3ème année
Réalisations du responsable dans le domaine de l’UE
A.BILLIONNET, Using Integer Programming to Solve the Train Platforming Problem. Transportation Science, 37, 2003, 213-222.
A.BILLIONNET and E.SOUTIF, Using a mixed integer programming tool for solving the 0-1 quadratic knapsack problem. INFORMS Journal on Computing, 16, 2004, 188-197.
A.BILLIONNET and E.SOUTIF, An exact method based on lagrangian decomposition for the 0-1 quadratic knapsack problem. European Journal of Operational Research , 157, 2004, 565-575.
A.BILLIONNET, S.ELLOUMI and L.GROUZ-DJERBI, Designing radio-mobile access networks based on Synchronous Digital Hierarchy rings. Computers & Operations Research, 32, 2005, 379-394.
A.BILLIONNET and S.ELLOUMI. Using a mixed integer quadratic progamming solver for the unconstrained quadratic 0-1 problem. A paraître dans Mathematical Programming.
Acronyme : perf
Spécialité : RES
3 ECTS
Niveau : 500
Semestre : S4
Titre : Performances des réseaux
Responsable : Bruno BAYNAT
Répartition hebdomadaire ou semestrielle
(30h/7 semaines)
Contenu
Toute conception de système doit nécessaire s'accompagner d'une évaluation de performances préalable. Cette évaluation de performances passe par une étape de modélisation, étape à la fois délicate et très importante : délicate car aucune méthodologie de modélisation n'existe et que seule l'étude de nombreux exemples peut aider à la conception d'un modèle valide très importante car toute l'analyse de performances et donc le dimensionnement du système reposent sur elle.
Expérience du responsable dans le domaine de l’UE
Bruno Baynat est Maître de Conférence en Informatique à l’Université Pierre et Marie Curie depuis 1991. Il travaille dans le domaine de la modélisation et de l’évaluation de performances des systèmes. Actuellement, ses recherches concernent le développement de modèles analytiques pour l’évaluation des performances des réseaux filaires (modèles de trafic ON/OFF, multicast, etc.), des réseaux Ad Hoc (couche MAC) et des réseaux cellulaires (GSM/GPRS/EDGE/UMTS). Son objectif est toujours de concevoir des modèles simples permettant à la fois une analyse qualitative du comportement de base du système et une analyse quantitative rapide des performances. Les modèles les plus couramment utilisés sont à base de processus stochastiques, de chaînes de Markov et de réseaux de files d’attentes.
Réalisations du responsable dans le domaine de l’UE
Baynat B., « La théorie des files d’attente : des chaînes de Markov aux réseaux à forme produit », éditions Hermès, ISBN 2-7462-0120-8, Paris, juin 2000.
M. Coupechoux, B. Baynat, T. Lestable, C. Bonnet et V. Kumar, « Improving the MAC Layer of Multi-Hop Netwlorks », Kluwer Wireless Communication Journal, Special Issue on SW’03, Vol. 29, pp. 71-100, Avril 2004.
M. Coupechoux, B. Baynat, C. Bonnet et V. Kumar, « CROMA – An Enhanced Dynamic Slot Allocation Protocol for MANETS », ACM MONET (Mobile Networks and Application), Special Issue on Algorithmic Solutions for Wireless, Mobile, Ad Hoc and Sensor Networks, Vol. 10, N°2, 2004.
G. Nogueira, B. Baynat et P. Eisenmann, « An analytical model for the dimensioning of a GPRS/EDGE network with a capacity constraint on group of cells », 11th Annual ACM International Conference on Mobile Computing and Networking (ACM MobiCom 2005), Cologne, Allemagne, août 2005.
B. Baynat et P. Eisenmann, « Towards an Erlang-like formula for GPRS/EDGE network engineering », 2004 IEEE International Conference on Communications (ICC 2004), Paris, France, juin 2004.
