Génération de colonnes

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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-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]

Notes et références[modifier | modifier le code]

  1. (en) Guy Desaulniers, Jacques Desrosiers et Marius M. Solomon, Column Generation, Springer-Verlag New York Inc,‎ 19 mai 2005, 358 p. (ISBN 0387254854)
  2. (en) Roberto Baldacci et Aristide Mingozzi, « A unified exact method for solving different classes of vehicle routing problems », Mathematical Programming (en), vol. 120, no 2,‎ septembre 2009, p. 347-380 (ISSN 0025-5610, DOI 10.1007/s10107-008-0218-9)