Inexact cuts in benders decomposition

作     者：Zakeri, G Philpott, AB Ryan, DM 

作者机构：Argonne Natl Lab Math Sci Div Argonne IL 60439 USA Univ Auckland Dept Engn Sci Operat Res Grp Auckland New Zealand 

出 版 物：《SIAM JOURNAL ON OPTIMIZATION》 (工业与应用数学会最优化杂志)

年 卷 期：2000年第10卷第3期

页      面：643-657页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：stochastic programming Benders decomposition inexact cuts 

摘      要：Benders decomposition is a well-known technique for solving large linear programs with a special structure. In particular, it is a popular technique for solving multistage stochastic linear programming problems. Early termination in the subproblems generated during Benders decomposition (assuming dual feasibility) produces valid cuts that are inexact in the sense that they are not as constraining as cuts derived from an exact solution. We describe an inexact cut algorithm, prove its convergence under easily verifiable assumptions, and discuss a corresponding Dantzig-Wolfe decomposition algorithm. The paper is concluded with some computational results from applying the algorithm to a class of stochastic programming problems that arise in hydroelectric scheduling.