Extended cross decomposition for mixed-integer linear programs with strong and weak linking constraints
Loading...
Authors
Ogbe, Emmanuel
Li, Xiang
Date
2018-11-02
Type
journal article
Language
Keyword
Benders decomposition , Cross decomposition , Dantzig–Wolfe decomposition , Mixed-integer linear programming , Risk-averse stochastic programming
Alternative Title
Abstract
Large-scale mixed-integer linear programming (MILP) problems, such as those from two-stage stochastic programming, usually have a decomposable structure that can be exploited to design efficient optimization methods. Classical Benders decomposition can solve MILPs with weak linking constraints (which are decomposable when linking variables are fixed) but not strong linking constraints (which are not decomposable even when linking variables are fixed). In this paper, we first propose a new rigorous bilevel decomposition strategy for solving MILPs with strong and weak linking constraints, then extend a recently developed cross decomposition method based on this strategy. We also show how to apply the extended cross decomposition method to two-stage stochastic programming problems with conditional-value-at-risk (CVaR) constraints. In the case studies, we demonstrate the significant computational advantage of the proposed extended cross decomposition method as well as the benefit of including CVaR constraints in stochastic programming.
Description
Citation
Ogbe, E., & Li, X. (2018). Extended cross decomposition for mixed-integer linear programs with strong and weak linking constraints. Computers & Chemical Engineering, 119, 237–257. doi:10.1016/j.compchemeng.2018.09.011
Publisher
Elsevier BV