Descomposició de Benders

La descomposició de Benders (anomenada en honor de Jacques F. Benders) és una tècnica en programació matemàtica que permet obtenir la solució de problemes de programació lineal que tenen una estructura de bloc especial. Aquesta estructura sovint ocorre en aplicacions tals com la programació estocàstica. A mesura que progressa cap a una solució, la descomposició de Benders afegeix només restriccions, per la qual cosa l'aproximació s'anomena de «generació de files»; contràriament, la descomposició de Dantzig-Wolfe utilitza «generació de columnes».

A mesura que progressa cap a una solució, la descomposició de Benders afegeix noves restriccions: és per això que aquest mètode és de «generació de files», en contrast amb la descomposició de Danzig-Wolfe, que utilitza la «generació de columnes».

Bibliografia

• J. F. Benders, «Partitioning procedures for solving mixed-variables programming problems», Numer. Math. 4, 3 (Sept. 1962), pp. 238–252. [1]
• Lasdon, Leon S. Optimization theory for large systems. Mineola, New York: Dover Publications, Inc., 2002, p. xiii+523.