Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Prise de décision optimale : programmation intégrale

Description

Cette séance de cours couvre la solution de problèmes de programmation entiers simples, y compris la relaxation des contraintes à la programmation linéaire standard. Il explore également le concept de coques convexes de solutions entières et l'application des plans de coupe Gomory. La séance de cours se termine par une discussion sur les méthodes de branche et liées pour les problèmes d'optimisation discrets.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Source officielle

Proximité ontologique

Informatique théorique

Algorithmes et structures de données: Optimisation combinatoire

Concepts associés (29)

Optimisation linéaire

thumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (x1, x2). La fonction-coût fc est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble admissible E est le pentagone vert. En optimisation mathématique, un problème d'optimisation linéaire demande de minimiser une fonction linéaire sur un polyèdre convexe. La fonction que l'on minimise ainsi que les contraintes sont décrites par des fonctions linéaires, d'où le nom donné à ces problèmes.

Optimisation linéaire en nombres entiers

L'optimisation linéaire en nombres entiers (OLNE) (ou programmation linéaire en nombres entiers (PLNE) ou integer programming (IP) ou Integer Linear Programming (ILP)) est un domaine des mathématiques et de l'informatique théorique dans lequel on considère des problèmes d'optimisation d'une forme particulière. Ces problèmes sont décrits par une fonction de coût et des contraintes linéaires, et par des variables entières.

Méthode des plans sécants

vignette|Application de la méthode des plans sécants au problème du voyageur de commerce. En mathématiques, et spécialement en optimisation linéaire en nombres entiers, la méthode des plans sécants, ou cutting plane method, est une méthode utilisée pour trouver une solution entière d'un problème d'optimisation linéaire. Elle fut introduite par Ralph E. Gomory puis étudiée par Gomory et Václav Chvátal. Le principe de la méthode est d'ajouter des contraintes au programme linéaire pour le raffiner, et le rapprocher des solutions intégrales.

Relaxation continue

En informatique théorique et en recherche opérationnelle, la relaxation continue est une méthode qui consiste à interpréter de façon continue un problème combinatoire ou discret. Cette méthode est utilisée afin d'obtenir des informations sur le problème discret initial et parfois même pour obtenir sa solution. Les problèmes discrets ou combinatoires sont en effet très difficiles à traiter en raison de l'explosion combinatoire et il est courant de les traiter par une méthode de séparation et évaluation (branch and bound en anglais) : la relaxation continue fait partie des algorithmes d'évaluation nécessaire à la mise en œuvre de cette méthode.

Séparation et évaluation

Un algorithme par séparation et évaluation, ou branch and bound en anglais, est une méthode générique de résolution de problèmes d'optimisation combinatoire. Cet algorithme a été introduit par Ailsa Land et Alison Harcourt (Doig) en 1960. L'optimisation combinatoire consiste à trouver un point minimisant une fonction, appelée coût, dans un ensemble dénombrable. Une méthode naïve pour résoudre ce problème est d'énumérer toutes les solutions du problème, de calculer le coût pour chacune, puis de donner le minimum.

Afficher plus

Séances de cours associées (48)

Programmation linéaire : correspondance bipartite pondérée

Couvre la programmation linéaire, la correspondance bipartite pondérée et les problèmes de couverture de sommet en optimisation.

Méthodes exactes : Branche et Liée MOOC: Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Explore l'algorithme Branch et Bound dans une optimisation discrète, en trouvant efficacement des solutions optimales en calculant des limites inférieures sur des sous-ensembles.

Optimisation discrète : relaxation MOOC: Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Explore la résolution de problèmes d'optimisation discrets en assouplissant les contraintes d'intégralité.

Algorithmes d'approximation

Couvre les algorithmes d'approximation pour les problèmes d'optimisation, la relaxation LP et les techniques d'arrondi aléatoire.

Hedging pour les LPs

Couvre le concept de couverture pour les programmes linéaires et la méthode simplex, en se concentrant sur la réduction des coûts et la recherche de solutions optimales.

Afficher plus

Concepts associés (29)

Optimisation linéaire

Optimisation linéaire en nombres entiers

Méthode des plans sécants

Relaxation continue

Séparation et évaluation

Afficher plus