Décomposition de Benders

La décomposition de Benders est une technique d'optimisation qui permet de trouver des solutions à des problèmes d'optimisation linéaire de très grande taille ayant une structure de blocs. On rencontre souvent cette structure dans les applications comme la programmation stochastique. Cet algorithme génère des contraintes au fur et à mesure de sa progression vers la solution. La technique porte le nom de Jacques F. Benders.

La stratégie derrière la décomposition de Benders peut être résumée ainsi : diviser pour mieux régner. Autrement dit, dans la décomposition de Benders, les variables du problème d'origine sont divisées en deux sous-ensembles de sorte qu'un problème maître de première étape est résolu sur le premier ensemble de variables, et les valeurs du deuxième ensemble de variables sont déterminées dans un second- sous-problème d'étape pour une solution de première étape donnée. Si le sous-problème détermine que les décisions fixes de la première étape sont en fait irréalisables, alors les coupes de Benders sont générées et ajoutées au problème principal, qui est ensuite résolu jusqu'à ce qu'aucune coupe ne puisse être générée. Puisque la décomposition de Benders ajoute de nouvelles contraintes au fur et à mesure qu'elle progresse vers une solution, l'approche est donc considérée comme une approche génération de lignes, ce qui contraste avec l'approche par décomposition de Dantzig-Wolfe basée sur la génération de colonnes.

Méthodologie

Supposons un problème qui se produit en deux étapes ou plus, où les décisions pour les étapes ultérieures reposent sur les résultats des étapes précédentes. Une tentative de décision de première étape peut être faite sans connaissance préalable de l'optimalité en fonction des décisions d'étapes ultérieures. Cette décision de première étape est le problème principal. Les étapes suivantes peuvent alors être analysées comme des sous-problèmes distincts. Les informations de ces sous-problèmes sont renvoyées au problème principal. Si les contraintes d'un sous-problème ont été violées, elles peuvent être ajoutées au problème principal. Le problème principal est alors résolu.

Le problème principal représente un ensemble convexe initial qui est en outre contraint par les informations recueillies à partir des sous-problèmes. Étant donné que l'espace réalisable ne fait que rétrécir à mesure que des informations sont ajoutées, la valeur objectif de la fonction principale fournit une limite inférieure sur la fonction objectif du problème global.

La décomposition de Benders est applicable aux problèmes avec une structure diagonale par blocs.

Formulation mathématique

Supposons un problème de structure suivante :

${\begin{aligned}&{\text{minimiser}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} +\mathbf {d} ^{\mathrm {T} }\mathbf {y} \\&{\text{tel que}}&&A\mathbf {x} +B\mathbf {y} \geq \mathbf {b} \\&&&y\in Y\\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}$

Où $A,B$ représentent les contraintes partagées par les deux étapes de variables et $Y$ représente l'ensemble des possibles pour $\mathbf {y}$. Notez que pour tout $\mathbf {\bar {y}} \in Y$ fixe, le problème résiduel est :

${\begin{aligned}&{\text{minimiser}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} +\mathbf {d} ^{\mathrm {T} }\mathbf {\bar {y}} \\&{\text{tel que}}&&A\mathbf {x} \geq \mathbf {b} -B\mathbf {\bar {y}} \\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}$

Le dual du problème résiduel est :

${\begin{aligned}&{\text{maximiser}}&&(\mathbf {b} -B\mathbf {\bar {y}} )^{\mathrm {T} }\mathbf {u} +\mathbf {d} ^{\mathrm {T} }\mathbf {\bar {y}} \\&{\text{tel que}}&&A^{\mathrm {T} }\mathbf {u} \leq \mathbf {c} \\&&&\mathbf {u} \geq \mathbf {0} \end{aligned}}$

En utilisant la double représentation du problème résiduel, le problème original peut être réécrit comme un problème Min-Max équivalent

$\min _{\mathbf {y} \in Y}\left[\mathbf {d} ^{\mathrm {T} }\mathbf {y} +\max _{\mathbf {u} \geq \mathbf {0} }\left\{(\mathbf {b} -B\mathbf {y} )^{\mathrm {T} }\mathbf {u} \mid A^{\mathrm {T} }\mathbf {u} \leq \mathbf {c} \right\}\right].$

La décomposition de Benders repose sur une procédure itérative qui choisit des valeurs successives de $\mathbf {y}$ sans tenir compte du problème interne, sauf via un ensemble de contraintes de coupe créées via un mécanisme de retour à partir du problème de maximisation. Bien que la formulation Min-Max soit écrite en termes de $(\mathbf {u} ,\mathbf {y} )$, pour un $\mathbf {\bar {y}}$ optimal, le $\mathbf {\bar {x}}$ correspondant peut être trouvé en résolvant le problème original avec $\mathbf {\bar {y}}$ corrigé.

Formulation du problème principal

Les décisions pour le problème de la première étape peuvent être décrites par le plus petit problème de minimisation

${\begin{aligned}&{\text{minimiser}}&&\mathbf {z} \\&{\text{tel que}}&&\{{\text{cuts}}\}\\&&&\mathbf {y} \in Y\\\end{aligned}}$

Initialement l'ensemble des coupes est vide. La résolution de ce problème principal constituera une "première estimation" d'une solution optimale au problème global, avec la valeur de $\mathbf {z}$ illimitée ci-dessous et $\mathbf {y}$ prendre n'importe quelle valeur réalisable.

L'ensemble des coupes sera rempli dans une séquence d'itérations en résolvant le problème de maximisation interne de la formulation Min-Max. Les coupes guident à la fois le problème principal vers un $\mathbf {y}$ optimal, s'il en existe un, et garantissent que $\mathbf {y}$ est réalisable pour le problème complet. L'ensemble de coupes définit la relation entre $\mathbf {y}$, $\mathbf {z}$ et implicitement $\mathbf {x}$.

Étant donné que la valeur de $z$ commence sans contrainte et que nous n'ajoutons des contraintes qu'à chaque itération, ce qui signifie que l'espace réalisable ne peut que rétrécir, la valeur du problème principal à toute itération fournit une borne inférieure sur la solution à l'ensemble problème. Si pour certains $\mathbf {\bar {y}}$ la valeur objective du problème maître est égale à la valeur de la valeur optimale du problème interne, alors selon la théorie de la dualité la solution est optimale.

Formulation du sous-problème

Le sous-problème considère la solution suggérée $\mathbf {\bar {y}}$ au problème maître et résout le problème de maximisation interne à partir de la formulation minimax. Le problème interne est formulé en utilisant la représentation duale :

${\begin{aligned}&{\text{maximiser}}&&(\mathbf {b} -B\mathbf {\bar {y}} )^{\mathrm {T} }\mathbf {u} +\mathbf {d} ^{\mathrm {T} }\mathbf {\bar {y}} \\&{\text{tel que}}&&A^{\mathrm {T} }\mathbf {u} \leq \mathbf {c} \\&&&\mathbf {u} \geq \mathbf {0} \end{aligned}}$

Alors que le problème principal fournit une borne inférieure sur la valeur du problème, le sous-problème est utilisé pour obtenir une borne supérieure. Le résultat de la résolution du sous-problème pour tout $\mathbf {\bar {y}}$ donné peut être soit une valeur optimale finie pour laquelle un point extrême $\mathbf {\bar {u}}$ peut être trouvé, une solution illimitée pour laquelle un rayon extrême $\mathbf {\bar {u}}$ dans le Cône asymptotique peut être trouvé, ou une constatation que le sous-problème est irréalisable.

Procédure

Chaque itération entre le problème principal et le sous-problème fournit une mise à jour des bornes supérieure et inférieure de la fonction objectif. Le résultat du sous-problème fournit soit une nouvelle contrainte à ajouter au problème maître, soit un certificat indiquant qu'aucune solution optimale finie n'existe pour le problème. La procédure se termine lorsqu'il est démontré qu'aucune solution optimale finie n'existe ou lorsque l'écart entre la borne supérieure et la borne inférieure est suffisamment petit. Dans un tel cas, la valeur de $\mathbf {\bar {x}}$ est déterminée en résolvant le problème des résidus primaires fixant $\mathbf {\bar {y}}$.

Formellement, la procédure commence avec la borne inférieure définie sur $-\inf$, la borne supérieure définie sur $\inf$ et les coupures dans le problème maître vides. Une solution initiale est produite en sélectionnant n'importe quel $\mathbf {\bar {y}} \in Y$. Ensuite, la procédure itérative commence et se poursuit jusqu'à ce que l'écart entre la borne supérieure et la borne inférieure soit au plus $\epsilon$ ou qu'il soit démontré qu'aucune solution optimale finie n'existe.

La première étape de chaque itération commence par mettre à jour la borne supérieure en résolvant le sous-problème étant donné la valeur la plus récente de $\mathbf {\bar {y}}$.

Il y a trois résultats possibles à la résolution du sous-problème.

Dans le premier cas, la valeur objective du sous-problème est illimitée au-dessus. Selon la théorie de la dualité, lorsqu'un problème dual a un objectif illimité, le problème primal correspondant est infaisable. Cela signifie que le choix de $\mathbf {\bar {y}}$ ne satisfait pas $A\mathbf {x} +B\mathbf {\bar {y}} \geq \mathbf {b}$ pour tout $\mathbf {x} \geq \mathbf {0}$. Cette solution peut être supprimée du problème maître en prenant un rayon extrême $\mathbf {\bar {u}}$ qui certifie que le sous-problème a un objectif illimité et en ajoutant une contrainte au maître affirmant que $(\mathbf {b} -B\mathbf {y} )^{\mathrm {T} }\mathbf {\bar {u}} \leq \mathbf {0}$.

Dans le second cas, le sous-problème est infaisable. Étant donné que le double espace réalisable du problème est vide, soit le problème d'origine n'est pas réalisable, soit il existe un rayon dans le problème primal qui certifie que la valeur objective est illimitée en dessous. Dans les deux cas, la procédure se termine.

Dans le troisième cas, le sous-problème a une solution optimale finie. Selon la théorie de la dualité pour les programmes linéaires, la valeur optimale du sous-problème est égale à la valeur optimale du problème original contraint sur le choix de $\mathbf {\bar {y}}$. Cela permet de mettre à jour la borne supérieure à la valeur de la solution optimale du sous-problème, si elle est meilleure que la borne supérieure courante. Étant donné un point extrême optimal $\mathbf {\bar {u}}$, cela donne également une nouvelle contrainte qui oblige le problème principal à considérer la valeur objective sous cette solution particulière en affirmant que $z\geq (\mathbf {b} -B\mathbf {y} )^{\mathrm {T} }\mathbf {\bar {u}} +\mathbf {d} ^{\mathrm {T} }\mathbf {y}$. Cela augmentera strictement la valeur de $z$ à la solution $\mathbf {\bar {y}}$ dans le problème maître si le choix de $\mathbf {\bar {y}}$ était sous-optimal.

Enfin, la dernière partie de chaque itération crée une nouvelle solution au problème maître en résolvant le problème maître avec la nouvelle contrainte. La nouvelle solution $(\mathbf {\bar {y}} ,z)$ est utilisée pour mettre à jour la borne inférieure. Si l'écart entre la meilleure limite supérieure et inférieure est inférieur à $\epsilon$ alors la procédure se termine et la valeur de $\mathbf {\bar {x}}$ est déterminée en résolvant le problème résiduel primal fixant $\mathbf {\bar {y}}$. Sinon, la procédure continue à l'itération suivante.

Références

• J. F. Benders, "Partitioning procedures for solving mixed-variables programming problems," Numer. Math. 4, 3 (Sept. 1962), pp. 238–252. [1]