Génération de colonnes
Cet article est une ébauche concernant l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Cet article ne cite pas suffisamment ses sources ().
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 ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
En informatique théorique et en recherche opérationnelle, la génération de colonnes est une méthode pour résoudre efficacement les problèmes d'optimisation linéaire 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-ensembles.
Description
[modifier | modifier le code]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
[modifier | modifier le code]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
[modifier | modifier le code]- problème de bin packing (cutting stock) (découpe en une ou plusieurs dimensions)
- problème de tournées de véhicules[2]
- planification d'équipages (en)
Notes et références
[modifier | modifier le code]- (en) Guy Desaulniers, Jacques Desrosiers et Marius M. Solomon, Column Generation, Springer-Verlag New York Inc, , 358 p. (ISBN 0-387-25485-4, lire en ligne)
- (en) Roberto Baldacci et Aristide Mingozzi, « A unified exact method for solving different classes of vehicle routing problems », Mathematical Programming, vol. 120, no 2, , p. 347-380 (ISSN 0025-5610, DOI 10.1007/s10107-008-0218-9)
