Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
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.
Propriétés
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 dus 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èmes traités efficacement par la génération de colonnes
↑(en) Guy Desaulniers, Jacques Desrosiers et Marius M. Solomon, Column Generation, Springer-Verlag New York Inc, , 358 p. (ISBN0-387-25485-4, lire en ligne)
