UCL - Etudes

Formations
Premier cycle
Deuxième cycle
Troisième cycle
Certificats (programmes non académiques)
Passerelles
Formation continue
Facultés et entités
Cadre académique
Réforme de Bologne
Accès aux études
Organisation des études
Lexique
Calendrier académique
Règlement des études et examens
Charte pédagogique
Renseignements généraux

Optimisation : programmation combinatoire [INMA2450]
[30h+15h exercices] 4 crédits

English version

Version imprimable

Cette activité se déroule pendant le 1er semestre

Enseignant(s):

Bernard Fortz (supplée Laurence Wolsey), Laurence Wolsey

Langue d'enseignement :

français

Niveau :

cours de 2ème cycle

>> Objectifs (en terme de compétences)
>> Objet de l'activité (principaux thèmes à aborder)
>> Résumé : Contenu et Méthodes
>> Autres informations (Pré-requis, Evaluation, Support, ...)
>> Autres crédits de l'activité dans les programmes

Objectifs (en terme de compétences)

Dans ce cours, nous examinons des méthodes efficaces pour résoudre des problèmes d'optimisation discrète qui sont posés en étudiant des graphes, la gestion de la production, la logistique, la conception de circuits, etc. Etant donné que la plupart des problèmes pratiques sont "difficiles", le but principal est de comprendre comment modéliser de tels problèmes et ensuite choisir un algorithme approprié - énumération implicite, méthode de coupes, décomposition, heuristique - afin d'obtenir une solution optimale ou avec une garantie d'être proche de l'optimum.

Objet de l'activité (principaux thèmes à aborder)

Dans ce cours nous examinons des méthodes différentes pour résoudre un problème d'optimisation avec des indivisibilités, ou des décisions oui/non concernant le choix d'une arête dans un graphe, l'achat d'une machine, l'utilisation d'un dépot, etc. De tels problèmes sont posés dans la construction d'un horaire de train ou d'avion, d'un tour dans un graphe, d'un plan de génération journalier d'électricité, etc. La théorie concerne les polyèdres, matrices, graphes et certains aspects de la complexité. Les approches algorithmiques étudiées sont l'énumeration implicite et les méthodes de coupes (branch-and-cut), relaxation lagrangienne, programmation dynamique et les algorithmes d'approximation.

Résumé : Contenu et Méthodes

Cours 1: Formulation de problèmes d'optimisation combinatoire et d'optimisation en nombres entiers.
Cours 2: Génération de bornes sur la valeur optimale et preuves d'optimalité.
PROBLEMES FACILES
Cours 3: Reconnaissance de problèmes faciles - flot dans un réseau, arbres
Cours 4: Problèmes de couplage et d'affectation
Cours 5: La distinction entre problèmes faciles et difficiles - éléments de complexité
PROBLEMES DIFFICILES
Cours 6: Enumération intelligente - l'algorithme d'énumération implicite (séparation et évaluation)
Cours 7: Relaxation lagrangienne- une approche par décomposition
Cours 8: Approche géométrique - algorithmes de coupes générales
Cours 9: L'utilisation de la structure - algorithmes de coupes specialisées - branch-and-cut
Cours10: Méthodes heuristiques pour trouver de bonnes solutions rapidement
AUTRES SUJETS
Cours 11: Problèmes résolus par programmation dynamique
Cours 12: Décomposition par génération de colonnes
Cours 13: Plus sur la modélisation et la résolution de problèmes

Autres informations (Pré-requis, Evaluation, Support, ...)

Une séance d'exercises a lieu toutes les deux semaines. Les étudiants doivent utiliser un système de modélisation et d'optimisation pour résoudre quelques instances pratiques. Ils doivent aussi programmer et tester un des algorithmes vu au cours.
REFERENCE: Integer Programming, L.A. Wolsey, Wiley, New York 1998.

Autres crédits de l'activité dans les programmes

ECGE3DS/SC

Diplôme d'études spécialisées en économie et gestion (Master in business administration) (Supply Chain Management)

(4 crédits)

INFO23

Troisième année du programme conduisant au grade d'ingénieur civil informaticien

(4 crédits)

INGE23/G

Troisième Ingénieur de gestion (Générale)

INGE23/I

Troisième Ingénieur de gestion (Internationale)

MAP22

Deuxième année du programme conduisant au grade d'ingénieur civil en mathématiques appliquées

(4 crédits)

MAP23

Troisième année du programme conduisant au grade d'ingénieur civil en mathématiques appliquées

(4 crédits)

MATH22/G

Deuxième licence en sciences mathématiques

(4 crédits)



Ce site a été conçu en collaboration avec ADCP, ADEF, CIO et SGSI
Responsable : Jean-Louis Marchand - Contact : secretaire@fsa.ucl.ac.be
Dernière mise à jour : 25/05/2005