Décomposition de Benders
De Wikipedia, l'encyclopédie encyclopedia
Pour les articles homonymes, voir 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.