Benders Decomposition for multi-stage stochastic mixed complementarity problems – Applied to a global natural gas market model

摘要: Abstract This paper presents and implements a Benders Decomposition type of algorithm for large-scale, stochastic multi-period mixed complementarity problems. The is applied to various multi-stage natural gas market models accounting power exertion by traders. Due the non-optimization nature problem, straightforward implementation traditional not possible. master subproblems can be derived from underlying optimization problems transformed into However, complete optimality cuts are added using variational inequality-based method developed in Gabriel Fuller (2010) . In this manner, an alternative derivation Stochastic MCP presented, thereby making approach more applicable broader audience. successfully solve with up 256 scenarios than 600 thousand variables, over 117 variables two first-stage capacity expansion variables. efficient solving two-stage computational time reduction other considerable would even larger if parallel were used. concludes discussion infrastructure results, illustrating impact hedging on investment timing optimal sizes.