Génération de colonne

La génération de colonne ou la génération de colonne retardé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 considérer explicitement toutes les variables. La prémisse est que la plupart des variables seront non basiques et supposeront 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 générer uniquement les variables qui ont le potentiel d’améliorer la fonction objective, 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 maître et le sous-problème. Le problème principal est le problème d’origine, seul un sous-ensemble de variables étant 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 maître est résolu — à partir de cette solution, nous sommes en mesure d’obtenir des prix doubles pour chacune des contraintes du problème maître. Cette information est ensuite utilisée 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 à coût réduit négatif a été identifiée. Cette variable est ensuite ajoutée au problème maître et le problème maître est à nouveau résolu. La résolution à nouveau 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 renvoie une solution avec un 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 stock de coupe. Une technique particulière en programmation linéaire qui utilise ce genre 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 médiane p capacitive.

Cet article relatif aux mathématiques appliquées est un talon. Vous pouvez aider Wikipedia en l’élargissant.