Optimisation combinatoire

Ce que vous allez apprendre

À la fin de ce cours, vous saurez :

Comprendre la notion de l’optimisation combinatoire ;
Modéliser un problème mono-objectif de la famille de l’optimisation combinatoire ;
Résoudre un modèle en nombres entiers à l’optimum par l’utilisation de la méthode du simplexe ;
Comprendre l’intérêt de la réduction de la taille d’une instance d’un problème avant sa résolution optimale ;
Résoudre un problème particulier (le sac à dos) par une approche spécifique optimale ;
Des techniques d’accélérations pour des résolutions optimales ;
Comprendre l’intérêt de l’injection de certaines coupes pour une résolution efficace optimale.

Description

Le cours vous permettra de vous familiariser avec certaines modélisations et méthodes de résolution des problèmes de l’optimisation combinatoire. Connaître l’intérêt d’utiliser une telle méthode optimale, ses limites, et être en mesure de mettre en place un code de cette dernière afin d’étudier son comportement et d’évaluer sa performance face à des instances caractérisant le problème étudié. Le contenu du cours s’appuie sur des définitions, des notions de bases et de résultats théoriques, qui seront appuyés par un ensemble d’exercices à traiter.

Format

Le cours est donné sous forme de sessions, qui sont structurées de la façon suivante : (i) un cours composé d'une version Web et d'une version PDF, et (ii) des activités composées de QCM d'auto-formation et d'exercices avec corrections. Afin de mieux assimiler le contenu de ce cours, vous devrez lire attentivement le contenu dédié au cours Web (une version PDF est disponible pour le téléchargement). La compréhension de cette présentation du cours est un atout pour comprendre comment aborder les exercices proposés avant de poursuivre vers les corrections suggérées. Notons aussi que la correction de chaque exercice mérite une bonne analyse avant de passer vers une autre correction.

Prérequis

• Algèbre linéaire (Matrices, inverse d’une matrice, … résolution d’un système linéaire par une méthode itérative …).
• Algorithme et complexité algorithmique.

Evaluation et Certification

QCM à la fin de chaque session.

Plan de cours

- Quelques exemples de la famille OC
- 1. Forme Générale d'un programme
  2. Rappel sur la résolution en continu
  Exercices
  QCM
- 1. Arbre de recherche : principe générique
  2. Exemple d’application d’une procédure SE
  Exercices
  QCM
- 1. Introduction
  2. Résolution (évaluation) des sous-problèmes induits
  Exercices
  QCM
- 1. Introduction
  2. Fixation d’une variable à l’optimum
  3. Une solution réalisable pour le problème (P)
  Exercices
  QCM
- 1. Méthodes exactes pour le knapsack à variables bivalentes
  Exercices
  QCM
- 1. Contraintes de couverture
  Exercices
  QCM
- 1. Introduction
  2. Etude d'un cas et généralisation
  Exercices
  QCM

Équipe pédagogique

Mhand HIFI

Catégories

Professeur des Universités en informatique à l'université de Picardie Jules Verne