Génération de colonnes

La génération de colonnes ou la génération de colonnes retardées 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 explicitement toutes les variables. L'idée est donc de commencer par résoudre le programme considéré avec seulement un sous-ensemble de ses variables. Ensuite, de manière itérative, les variables qui ont le potentiel d'améliorer la fonction objective sont ajoutées au programme. Une fois qu'il est possible de démontrer que l'ajout de nouvelles variables n'améliorerait plus la valeur de la fonction objective, la procédure s'arrête. L'espoir lors de l'application d'un algorithme de génération de colonnes est que seule une très petite fraction des variables sera générée. Cet espoir est soutenu par le fait que dans la solution optimale, la plupart des variables ne seront pas de base et prendront une valeur de zéro, de sorte que la solution optimale peut être trouvée sans elles.

Dans de nombreux cas, cette méthode permet de résoudre de grands programmes linéaires qui seraient autrement insolubles. L'exemple classique d'un problème où elle est utilisée avec succès est le problème de la découpe de stock . 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 des équipes , le routage des véhicules et le problème de la p-médiane capacitive.

L'algorithme considère deux problèmes : le problème principal et le sous-problème. Le problème principal est le problème d'origine dont seul un sous-ensemble de variables est pris en compte. Le sous-problème est un nouveau problème créé pour identifier une variable d'amélioration ( c'est-à-dire qui peut améliorer la fonction objective du problème principal).

L'algorithme se déroule ensuite comme suit :

1. Initialiser le problème maître et le sous-problème
2. Résoudre le problème principal
3. Rechercher une variable d'amélioration avec le sous-problème
4. Si une variable d'amélioration est trouvée : ajoutez-la au problème principal puis passez à l'étape 2
5. Sinon : La solution du problème principal est optimale. Arrêtez.

La partie la plus difficile de cette procédure est de trouver une variable qui puisse améliorer la fonction objective du problème principal. Cela peut être fait en trouvant la variable avec le coût réduit le plus négatif (en supposant sans perte de généralité que le problème est un problème de minimisation). Si aucune variable n'a un coût réduit négatif, alors la solution actuelle du problème principal est optimale.

Lorsque le nombre de variables est très grand, il n'est pas possible de trouver une variable améliorante en calculant l'ensemble des coûts réduits et en choisissant une variable à coût réduit négatif. L'idée est donc de calculer uniquement la variable ayant le coût réduit minimum. Cela peut être fait en utilisant un problème d'optimisation appelé sous-problème de tarification qui dépend fortement de la structure du problème original. La fonction objective du sous-problème est le coût réduit de la variable recherchée par rapport aux variables duales courantes, et les contraintes imposent que la variable obéisse aux contraintes naturelles. La méthode de génération de colonnes est particulièrement efficace lorsque cette structure permet de résoudre le sous-problème avec un algorithme efficace, typiquement un algorithme combinatoire dédié .

Nous détaillons maintenant comment et pourquoi calculer le coût réduit des variables. Considérons le programme linéaire suivant sous forme standard :

que nous appellerons le problème primal ainsi que son programme linéaire dual :

De plus, soient et des solutions optimales pour ces deux problèmes qui peuvent être fournies par tout solveur linéaire. Ces solutions vérifient les contraintes de leur programme linéaire et, par dualité , ont même valeur de fonction objectif ( ) que nous appellerons . Cette valeur optimale est fonction des différents coefficients du problème primal : . Notons qu'il existe une variable duale pour chaque contrainte du modèle linéaire primal. Il est possible de montrer qu'une variable duale optimale peut s'interpréter comme la dérivée partielle de la valeur optimale de la fonction objectif par rapport au coefficient du membre de droite des contraintes : ou sinon . Plus simplement, indique de combien augmente localement la valeur optimale de la fonction objectif lorsque le coefficient augmente d'une unité.

Considérons maintenant qu'une variable n'était pas considérée jusqu'alors dans le problème primal. Notons que cela revient à dire que la variable était présente dans le modèle mais prenait une valeur nulle. Nous allons maintenant observer l'impact sur le problème primal du changement de la valeur de de à . Si et sont respectivement les coefficients associés à la variable dans la fonction objective et dans les contraintes alors le programme linéaire est modifié comme suit :

Afin de savoir s'il est intéressant d'ajouter la variable au problème ( c'est à dire de lui laisser prendre une valeur non nulle), on veut savoir si la valeur de la fonction objectif de ce nouveau problème diminue lorsque la valeur de la variable augmente. En d'autres termes, on veut savoir . Pour cela, notons que peut s'exprimer en fonction de la valeur de la fonction objectif du problème primal initial : . On peut alors calculer la dérivée qui nous intéresse :

En d'autres termes, l'impact du changement de valeur sur la valeur se traduit par deux termes. D'une part, ce changement impacte directement la fonction objective et d'autre part, le côté droit des contraintes est modifié ce qui a un impact sur les variables optimales dont l'ampleur est mesurée à l'aide des variables duales . La dérivée est généralement appelée coût réduit de la variable et sera notée dans ce qui suit.