Génération de colonnes

Contenus

Lorsqu’un programme linéaire possède beaucoup de variables, il n’est pas envisageable de le résoudre par un simplexe. La génération de colonnes permet de générer les variables utiles au fur et à mesure jusqu’à obtenir une solution optimale. L’objectif de cette méthode est de résoudre un problème réduit avec un ensemble limité de variables.

Le problème initial d’une génération de colonnes est appelé problème maître, et le problème réduit est appelé problème restreint.

Le problème restreint d’une génération de colonnes est plus simple à résoudre, mais si l’ensemble de ses variables ne contient pas celles qui donne la solution optimale pour le problème maître, pour atteindre la solution optimale du problème maître, il faut rajouter au problème restreint des variables pouvant être utilisées pour améliorer la solution.

Le problème consistant à chercher la meilleure variable à rajouter dans le problème restreint est appelé sous-problème associé au problème maître (ou oracle). Il a comme objectif de trouver la variable (ou colonne) de coût réduit minimum (c-à-d. la plus prometteuse pour améliorer la solution).

Le coût réduit des variables est calculé à l’aide des variables duales obtenues après la résolution du problème restreint. Le point du dual ainsi utilisé dans le sous problème est appelé point de séparation. Souvent, il s’agit d’une solution optimale du dual du problème restreint.

On considère le programme linéaire continu (LP) suivant :

Nous supposons que le nombre de variables de T est trop grand pour que le problème (LP) puisse être résolu en temps raisonnable, et que nous voulions le résoudre par génération de colonnes. Nous cherchons donc à résoudre le problème restreint associé au problème maître avec un ensemble restreint de variables noté R_l. Il faut que le problème restreint soit réalisable. Il est possible d’utiliser des colonnes simples par exemple des colonnes aléatoires, ou encore celles issues d’une solution faisable obtenue à partir d’une heuristique.

Le problème (RLP) est maintenant de taille réduite et sera plus facile à résoudre par un solveur. Cette résolution nous fournira les valeurs optimales des variables duales v_j associées aux contraintes. Ces valeurs sont passées au sous problème qui nous permet d’obtenir la ou les colonnes à rajouter dans l’ensemble R_l.

Le calcul du coût réduit nous permet de savoir si une colonne a fait diminuer la valeur de l’objectif (et donc de l’améliorer).

Puisque (LP) est un problème de minimisation, le sous problème cherche aussi à minimiser ce coût réduit. Si le coût réduit minimum est positif, alors aucune colonne ne peut être ajoutée au problème restreint (RLP) pour améliorer l’objectif. La solution optimale du problème restreint est donc une solution optimale du problème maître (LP). Sinon, on rajoute une ou des colonnes parmi celles ayant un coût réduit négatif en faisant une mise à jour de l’ensemble R_l et on résout après le nouveau problème restreint (RLP).