Décomposition de Benders

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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. Il est donc considéré 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.

Références[modifier | modifier le code]

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