Generation de colonnes
- Generation de colonnes
-
Génération de colonnes
La génération de colonnes est une méthode pour résoudre efficacement les programmes linéaires de grande taille. Elle repose sur la décomposition de Dantzig et Wolfe, qui consiste à décomposer l'ensemble des contraintes en deux sous ensembles.
L'idée centrale est que les programmes linéaires de grande taille ont trop de variables (ou colonnes) pour qu'on puisse les représenter toutes de manière explicite. A l'optimum, la plupart des variables sont hors base et, très souvent, la plupart d'entre elles sont nulles, c'est-à-dire que seul un (petit) sous-ensemble de variables doit être pris en compte pour résoudre le problème.
Une méthode utilisant la génération de colonnes initialise le programme linéaire avec un sous-ensemble de colonnes de petite taille. Le mécanisme de la génération de colonnes consiste alors à générer, au sein d'un algorithme à plusieurs étapes, les variables qui sont susceptibles d'améliorer la solution courante, c'est-à-dire celles qui ont des coûts réduits négatifs.
L'efficacité de la méthode est très dépendante du mécanisme utilisé pour générer des colonnes. En effet, le sous-problème à résoudre est souvent NP-difficile.
Les méthodes utilisant la génération de colonnes ont souvent des problèmes de convergence dû au fait que le problème dual est très peu contraint au début de la méthode. En pratique, ces problèmes vont amener la méthode à effectuer un grand nombre d'itérations qui ne permettent plus d'améliorer la solution courante.
Problème traités efficacement par la génération de colonnes
|
Articles en rapport avec la convexité |
| Géométrie convexe |
|
| Interactions géométrie-analyse |
|
| Analyse convexe |
|
| Utilisations de la convexité |
|
Catégories : Algorithme d'optimisation | Recherche opérationnelle
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Generation de colonnes de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Génération De Colonnes — La génération de colonnes est une méthode pour résoudre efficacement les programmes linéaires de grande taille. Elle repose sur la décomposition de Dantzig et Wolfe, qui consiste à décomposer l ensemble des contraintes en deux sous ensembles. L… … Wikipédia en Français
Génération de colonnes — La génération de colonnes est une méthode pour résoudre efficacement les programmes linéaires de grande taille[1]. Elle repose sur la décomposition de Dantzig Wolfe (en), qui consiste à décomposer l ensemble des contraintes en deux sous… … Wikipédia en Français
Generation — Génération Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom … Wikipédia en Français
Génération — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Génération », sur le Wiktionnaire (dictionnaire universel) Le mot génération désigne l action d… … Wikipédia en Français
Vieille génération — Génération Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom … Wikipédia en Français
Crise générationnelle — Génération Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom … Wikipédia en Français
Optimisation linéaire — En optimisation, qui est une branche des mathématiques, un problème d optimisation linéaire est un problème d optimisation dans lequel on minimise une fonction linéaire sur un polyèdre convexe. La fonction coût et les contraintes peuvent donc… … Wikipédia en Français
Branch and price — est une méthode d optimisation combinatoire pour résoudre des problèmes d optimisation linéaire en nombres entiers. Cette méthode combine l algorithme du branch and bound classique avec une génération de colonnes à chaque nœud de l arbre.… … 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
