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

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

0.00 Avg rating0 Votes
Article ID: iaor2013499
Volume: 226
Issue: 2
Start Page Number: 341
End Page Number: 353
Publication Date: Apr 2013
Journal: European Journal of Operational Research
Authors:
Keywords: Benders decomposition, natural gas markets, stochastic linear programme, hedging
Abstract:

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

Reviews

Required fields are marked *. Your email address will not be published.