Non-convex nested Benders decomposition
提出一种新分解算法NC-NBD，用于求解多阶段非凸混合整数非线性规划，通过分段线性松弛和嵌套Benders分解迭代逼近全局最优解，并证明有限步内收敛到ε最优解，在中等规模机组组合问题上表现良好。
Abstract We propose a new decomposition method to solve multistage non-convex mixed-integer (stochastic) nonlinear programming problems (MINLPs). We call this algorithm non-convex nested Benders decomposition (NC-NBD). NC-NBD is based on solving dynamically improved mixed-integer linear outer approximations of the MINLP, obtained by piecewise linear relaxations of nonlinear functions. Those MILPs are solved to global optimality using an enhancement of nested Benders decomposition, in which regularization, dynamically refined binary approximations of the state variables and Lagrangian cut techniques are combined to generate Lipschitz continuous non-convex approximations of the value functions. Those approximations are then used to decide whether the approximating MILP has to be dynamically refined and in order to compute feasible solutions for the original MINLP. We prove that NC-NBD converges to an $$\varepsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ε</mml:mi> </mml:math> -optimal solution in a finite number of steps. We provide promising computational results for some unit commitment problems of moderate size.