2023-2024 / MATH0462-1

Discrete optimization

Durée

30h Th, 20h Pr, 25h Proj.

Nombre de crédits

 Master en science des données, à finalité5 crédits 
 Master : ingénieur civil électricien, à finalité5 crédits 
 Master : ingénieur civil en génie de l'énergie, à finalité5 crédits 
 Master : ingénieur civil en informatique, à finalité5 crédits 
 Master : ingénieur civil en science des données, à finalité5 crédits 
 Master en sciences informatiques, à finalité5 crédits 
 Bachelier en sciences mathématiques6 crédits 
 Master en sciences mathématiques, à finalité6 crédits 

Enseignant

Quentin Louveaux

Langue(s) de l'unité d'enseignement

Langue anglaise

Organisation et évaluation

Enseignement au deuxième quadrimestre

Horaire

Horaire en ligne

Unités d'enseignement prérequises et corequises

Les unités prérequises ou corequises sont présentées au sein de chaque programme

Contenus de l'unité d'enseignement

Considérons un représentant commercial d'une entreprise qui doit visiter 20 clients potentiels dans 20 villes différentes. Une question naturelle que peut se poser le représentant est de savoir dans quel ordre il va visiter les clients afin de minimiser la distance parcourue. Ce problème célèbre mieux connu sous le nom du problème de voyageur de commerce est l'exemple typique du problème d'optimisation discrète. On dispose d'un nombre fini de solutions possibles (ici les 20! possibles permutations des villes) et pourtant il est pratiquement impossible de les tester toutes. Si on pouvait en tester un milliard par seconde, dans ce cas-ci il nous faudrait environ 77 ans pour toutes les parcourir.
Le problème de voyageur de commerce n'est qu'un exemple parmi tant d'autres de problèmes d'optimisation discrète. En effet, en particulier les problèmes où des décisions binaires (oui ou non par exemple) doivent se prendre sont légion dans les applications pratiques.
Au niveau du contenu du cours, dans un premier temps nous allons nous concentrer sur la modélisation de problèmes discrets sous forme de programmes linéaires en nombres entiers. Nous discuterons quelques principes pour formuler des problèmes et nous attarderons à ce qui fait une bonne formulation.
Ensuite, la deuxième partie du cours concernera les techniques de résolution des problèmes en nombres entiers: principalement branch-and-bound, branch-and-cut, relaxation lagrangienne, programmation dynamique, et algorithmes d'approximation. Nous discutons également quelques cas particuliers de problèmes discrets très importants et que l'on peut résoudre efficacement: les problèmes de flot et d'affectation.

Acquis d'apprentissage (objectifs d'apprentissage) de l'unité d'enseignement

A l'issue de ce cours, l'étudiant




  • pourra formuler un problème réel comme un problème d'optimisation en nombres entiers
  • pourra comparer deux formulations d'un même problème
  • connaîtra les principales méthodes pour résoudre les problèmes d'optimisation en nombres entiers.
  • pourra reconnaître un problème d'optimisation discrète qui peut être résolu en temps polynomial
Ce cours contribue aux acquis d'apprentissage I.1, I.2, II.1, III.1, III.2, III.4, IV.1, VI.1, VI.2, VI.3, VII.3, VII.4, VII.5 du programme d'ingénieur civil en génie biomédical.

Ce cours contribue aux acquis d'apprentissage I.1, I.2, I.3, II.1, III.1, III.2, III.4, IV.1, IV.4, VI.1, VI.2, VI.3, VII.3, VII.4, VII.5 du programme d'ingénieur civil en science des données.

Ce cours contribue aux acquis d'apprentissage I.1, I.2, II.1, III.1, III.2, III.4, IV.1, VI.1, VI.2, VI.3, VII.3, VII.4, VII.5 du programme d'ingénieur civil électricien.

Ce cours contribue aux acquis d'apprentissage I.1, I.2, II.1, III.1, III.2, III.4, IV.1, IV.3, VI.1, VI.2, VI.3, VII.3, VII.4, VII.5 du programme d'ingénieur civil en informatique.

 

Savoirs et compétences prérequis

Un cours de base en programmation linéaire est préférable.

Activités d'apprentissage prévues et méthodes d'enseignement

Des séances d'exercices en salle sont organisées chaque semaine.

Trois devoirs de modélisation sont demandés en cours d'année.

Mode d'enseignement (présentiel, à distance, hybride)

Cours donné exclusivement en présentiel

Lectures recommandées ou obligatoires et notes de cours

La référence principale est :

L. Wolsey, Integer Programming. Wiley, 1998.

Modalités d'évaluation et critères

Examen(s) en session

Toutes sessions confondues

- En présentiel

évaluation écrite ( questions ouvertes )

Travail à rendre - rapport


Explications complémentaires:

L'examen est un examen écrit de théorie et d'exercices.

L'examen compte pour 2/3 de la note finale. Les trois devoirs en cours d'année comptent pour 1/3 de la note finale.

Stage(s)

Remarques organisationnelles et modifications principales apportées au cours

Le cours se donne au second quadrimestre.

Tous les documents relatifs au cours sont disponibles sur ecampus.

Contacts

Association d'un ou plusieurs MOOCs