Génération de colonnes - Column generation

La génération de colonnes ou la génération de colonnes différée est un algorithme efficace pour résoudre de grands programmes linéaires .

L'idée générale est que de nombreux programmes linéaires sont trop volumineux pour prendre en compte toutes les variables explicitement. Le principe est que la plupart des variables seront non basiques et prendront une valeur de zéro dans la solution optimale. Pour cette raison, seul un sous-ensemble de variables doit être considéré en théorie lors de la résolution du problème. La génération de colonnes exploite cette idée pour ne générer que les variables qui ont le potentiel d'améliorer la fonction objectif, c'est-à-dire de trouver des variables à coût réduit négatif (en supposant sans perte de généralité que le problème est un problème de minimisation).

Le problème à résoudre est divisé en deux problèmes: le problème principal et le sous-problème. Le problème principal est le problème d'origine avec seulement un sous-ensemble de variables considéré. Le sous-problème est un nouveau problème créé pour identifier une nouvelle variable. La fonction objective du sous-problème est le coût réduit de la nouvelle variable par rapport aux variables doubles actuelles, et les contraintes exigent que la variable obéisse aux contraintes naturelles.

Le processus fonctionne comme suit. Le problème principal est résolu - à partir de cette solution, nous pouvons obtenir des prix doubles pour chacune des contraintes du problème principal. Ces informations sont ensuite utilisées dans la fonction objective du sous-problème. Le sous-problème est résolu. Si la valeur objective du sous-problème est négative, une variable avec un coût réduit négatif a été identifiée. Cette variable est ensuite ajoutée au problème principal et le problème principal est résolu à nouveau. La résolution du problème principal génèrera un nouvel ensemble de valeurs doubles et le processus est répété jusqu'à ce qu'aucune variable de coût réduit négative ne soit identifiée. Le sous-problème retourne une solution à coût réduit non négatif, nous pouvons conclure que la solution au problème maître est optimale.

Dans de nombreux cas, cela permet de résoudre de grands programmes linéaires qui étaient auparavant considérés comme insolubles. L'exemple classique d'un problème où cela est utilisé avec succès est le problème du matériel de coupe . Une technique particulière de programmation linéaire qui utilise ce type d'approche est l' algorithme de décomposition de Dantzig – Wolfe . De plus, la génération de colonnes a été appliquée à de nombreux problèmes tels que la planification de l'équipage , le routage des véhicules et le problème de la p-médiane capacitive .