Convergence properties of generalized Benders decompositions

Abstract: "This paper addresses two major issues related to the convergence of generalized Benders decomposition which is an algorithm for the solution of mixed integer linear and nonlinear programming problems. First, it is proved that a mixed integer nonlinear programming formulation with zero nonlinear programming relaxation gap requires only one Benders cut in order to converge, namely the cut corresponding to the optimal solution. This property indicates the importance of developing tight formulations for integer programs. Second, it is demonstrated that the application of generalized Benders decomposition to nonconvex problems does not always lead to the global optimum for these problems; it may not even lead to a local minimum.It is shown that this property follows from the fact that every local optimum of a nonlinear program gives rise to a local optimum in the projected problem of Benders. Examples are given to illustrate the properties."