Approche polyèdrale
- Approche polyèdrale
-
Approche polyèdrale
Le problème fondamental de l'approche polyèdrale est le suivant:
- Etant donné un ensemble X de points de l'espace Euclidien, déterminer un système d'inégalités linéaire décrivant l'enveloppe convexe de X.
Généralement X est un ensemble de points à coordonnées entières (voire en 0-1) qui représente les solutions réalisables d'un programme linéaire en nombres entiers. A l'origine cette approche a été introduite par Jack Edmonds qui donna la première caractérisation du polytope des couplages d'un graphe, c'est-à-dire de l'enveloppe convexe des vecteurs caractéristiques (dans {0,1}E) des couplages d'un graphe G = (V,E).
Le succès de l'opération a une conséquence directe algorithmique puisqu'elle réduit ainsi le problème d'optimiser sur X à un problème facile de programmation linéaire classique. Ceci est rendu possible à la condition toutefois de posséder un algorithme polynomial pour séparer les contraintes linéaires (c'est-à-dire décider si un point donné de l'espace appartient ou non au polyèdre défini par les contraintes, et sinon à trouver un hyperplan de séparation). Ce résultat fondamental est connu sous le nom de théorème séparation/optimisation.
Dans les faits, il existe un lien étroit entre la complexité algorithmique de l'optimisation sur X et la connaissance d'une description simple de conv(X). Pour beaucoup de problèmes polynomiaux une telle description est connue.
|
Articles en rapport avec la convexité |
| Géométrie convexe |
|
| Interactions géométrie-analyse |
|
| Analyse convexe |
|
| Utilisations de la convexité |
|
Portail de la géométrie
Catégories : Algorithmique et convexité | Optimisation combinatoire
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Approche polyèdrale de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Approche polyedrale — Approche polyèdrale Le problème fondamental de l approche polyèdrale est le suivant: Etant donné un ensemble X de points de l espace Euclidien, déterminer un système d inégalités linéaire décrivant l enveloppe convexe de X. Généralement X est un… … Wikipédia en Français
Theoreme optimisation/separation — Théorème optimisation/séparation Le théorème Optimisation/Séparation est une conséquence de la méthode de l ellipsoïde. Il constitue un résultat (très difficile à montrer) majeur en optimisation combinatoire qui fait le lien entre l approche… … Wikipédia en Français
Théorème Optimisation/Separation — Théorème optimisation/séparation Le théorème Optimisation/Séparation est une conséquence de la méthode de l ellipsoïde. Il constitue un résultat (très difficile à montrer) majeur en optimisation combinatoire qui fait le lien entre l approche… … Wikipédia en Français
Théorème Optimisation/Séparation — Le théorème Optimisation/Séparation est une conséquence de la méthode de l ellipsoïde. Il constitue un résultat (très difficile à montrer) majeur en optimisation combinatoire qui fait le lien entre l approche polyèdrale et l algorithmique. Ce… … Wikipédia en Français
Théorème optimisation/séparation — Le théorème Optimisation/Séparation est une conséquence de la méthode de l ellipsoïde. Il constitue un résultat (très difficile à montrer) majeur en optimisation combinatoire qui fait le lien entre l approche polyèdrale et l algorithmique. Ce… … Wikipédia en Français
PLNE — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… … Wikipédia en Français
Programmation lineaire — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… … Wikipédia en Français
Programmation linéaire — En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont également vrais si l… … Wikipédia en Français
Programmation linéaire en nombre entiers — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… … Wikipédia en Français
Programmation linéaire en nombres entiers — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… … Wikipédia en Français
