Décomposition de Benders

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.

Supposons un problème de structure suivante :

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

${\displaystyle {\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 :

${\displaystyle {\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

${\displaystyle \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 ${\displaystyle \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 ${\displaystyle (\mathbf {u} ,\mathbf {y} )}$, pour un ${\displaystyle \mathbf {\bar {y}} }$ optimal, le ${\displaystyle \mathbf {\bar {x}} }$ correspondant peut être trouvé en résolvant le problème original avec ${\displaystyle \mathbf {\bar {y}} }$ corrigé.

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 ${\displaystyle \mathbf {\bar {x}} }$ est déterminée en résolvant le problème des résidus primaires fixant ${\displaystyle \mathbf {\bar {y}} }$.

Formellement, la procédure commence avec la borne inférieure définie sur ${\displaystyle -\inf }$, la borne supérieure définie sur ${\displaystyle \inf }$ et les coupures dans le problème maître vides. Une solution initiale est produite en sélectionnant n'importe quel ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \mathbf {\bar {y}} }$ ne satisfait pas ${\displaystyle A\mathbf {x} +B\mathbf {\bar {y}} \geq \mathbf {b} }$ pour tout ${\displaystyle \mathbf {x} \geq \mathbf {0} }$. Cette solution peut être supprimée du problème maître en prenant un rayon extrême ${\displaystyle \mathbf {\bar {u}} }$ qui certifie que le sous-problème a un objectif illimité et en ajoutant une contrainte au maître affirmant que ${\displaystyle (\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 ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle z\geq (\mathbf {b} -B\mathbf {y} )^{\mathrm {T} }\mathbf {\bar {u}} +\mathbf {d} ^{\mathrm {T} }\mathbf {y} }$. Cela augmentera strictement la valeur de ${\displaystyle z}$ à la solution ${\displaystyle \mathbf {\bar {y}} }$ dans le problème maître si le choix de ${\displaystyle \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 ${\displaystyle (\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 à ${\displaystyle \epsilon }$ alors la procédure se termine et la valeur de ${\displaystyle \mathbf {\bar {x}} }$ est déterminée en résolvant le problème résiduel primal fixant ${\displaystyle \mathbf {\bar {y}} }$. Sinon, la procédure continue à l'itération suivante.

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