Non-convex nested Benders decomposition

• 成果类型: Article
• 署名作者: Fuellner, Christian; Rebennack, Steffen
• 署名单位: Helmholtz Association; Karlsruhe Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01740-0
• 发表日期: 2022
• 页码: 987-1024
• 关键词: global optimization; linear-programs; integer; constraints; models; branch; bounds

摘要

We propose a new decomposition method to solve multistage non-convex mixedinteger (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 e-optimal solution in a finite number of steps. We provide promising computational results for some unit commitment problems of moderate size.