Aller au sommaire principal

ULB - Université libre de Bruxelles

 

AIDE | QUITTER

   

Année académique 2017-2018
24/05/2019
Image transparente
Dernière modification : le 18/09/2015 par LABBE, Martine

Langue/Language


Combinatorial optimization
INFO - F424

I. Informations générales
Intitulé de l'unité d'enseignement * Combinatorial optimization
Langue d'enseignement * Enseigné en anglais
Niveau du cadre de certification * Niveau 7 (2e cycle-MA/MS/MA60)
Discipline * Informatique
Titulaire(s) * [y inclus le coordonnateur] Michaël POSS (coordonnateur), Martine LABBE
II. Place de l'enseignement
Unité(s) d'enseignement co-requise(s) *
Unité(s) d'enseignement pré-requise(s) *
Connaissances et compétences pré-requises * Base de la programmation linéaire et l'optimisation des réseaux.
Programme(s) d'études comprenant l'unité d'enseignement - M-INFOS - Master en sciences informatiques (5 crédits, optionnel)
- M-IRIFS - Master en ingénieur civil en informatique, à finalité spécialisée (5 crédits, optionnel)
III. Objectifs et méthodologies
Contribution de l'unité d'enseignement au profil d'enseignement *
Objectifs de l'unité d'enseignement (et/ou acquis d'apprentissages spécifiques) *

Savoir modéliser et résoudre des problèmes d'optimisation combinatoire.

Contenu de l'unité d'enseignement *

Ce cours présente les méthodes de base pour la résolution de problèmes d'optimisation combinatoire et de programmation linéaire en variables booléennes, entières ou mixtes. Il comprend 13 chapitres intitulés (i) formulations, (ii) optimalité, relaxation et bornes, (iii) problèmes bien résolus, (iv) couplages et affectations, (v) programmation dynamique, (vi) complexité et réduction de problèmes, (vii) branch and bound, (viii) algorithmes de plans coupants, (ix) inégalités valides fortes, (x) dualité lagrangienne, (xi) algorithmes de génération de colonnes, (xii) algorithmes heuristiques, (xiii) de la théorie vers les solutions.

Méthodes d'enseignement et activités d'apprentissages *

24 heures de cours magistral, 12h d'exercices, un projet

Support(s) de cours indispensable(s) * Non
Autres supports de cours
Références, bibliographie et lectures recommandées *

WOLSEY, L. (1998). Integer Programming, Wiley.

IV. Evaluation
Méthode(s) d'évaluation *

Examen écrit d'exercices (20%), examen oral de théorie (40%) et évaluation du projet (40%)

Construction de la note (en ce compris, la pondération des notes partielles) *

Examen écrit d'exercices (20%), examen oral de théorie (40%) et évaluation du projet (40%)

Langue d'évaluation *

Français ou anglais

V. Organisation pratique
Institution organisatrice * ULB
Faculté gestionnaire * Sciences
Quadrimestre * Deuxième quadrimestre (NRE : 18370)
Horaire * Deuxième quadrimestre
Volume horaire
VI. Coordination pédagogique
Contact *

Martine Labbé,  Campus de la Plaine Bâtiment NO Local 2.N3.215

Lieu d’enseignement *

Campus Plaine

VII. Autres informations relatives à l’unité d’enseignement
Remarques

Retour aux détails du cursus
Image transparente
Passer directement au début de la page
Version: 8.1.1.17