Operations Research Seminar: Steffen Rebennack

Tailored Benders Decomposition for a Long-Term Power Expansion Model with Short-Term Demand Response

Steffen Rebennack, Karlsruhe Institute of Technology (KIT)

Joint work with Timo Lohmann
 
Abstract: We present a long-term power generation expansion planning model that features a long planning horizon, an hourly time resolution, multiperiod investment and retirement decisions, transmission constraints, start-up restrictions, and short-term demand response. Demand response is the capability of power load to react to short-term changes in electricity prices. It plays an increasingly important role in today’s electricity markets but has not been taken into consideration in long-term power generation expansion planning problems, which mostly treat demand as perfectly inelastic. Given mild assumptions for the underlying demand function, the resulting model is a large-scale, concave, linearly constrained maximization problem. We exploit the model structure by developing a new approach to generalized Benders decomposition (GBD). In particular, we present two algorithmic ideas: (1) solving the nonlinear Benders subproblem as a linear programming (LP) problem with the aid of dynamic linear overestimation, referred to as the LP-based method, and (2) directly calculating all necessary optimal primal and dual variable values, referred to as the calculation-based method. We consider three special cases of our expansion planning model and show that solving mathematical programming problems can become entirely obsolete in the calculation-based method. We demonstrate the efficiency of all proposed algorithms for the Texas power system, comparing our tailored decomposition methods to a monolithic approach and a state-of-the-art GBD implementation. Our LP-based method is up to 3,822 times faster than the monolithic approach and up to 55 times faster than the GBD. The calculation-based method dramatically improves the solution time, being an average factor of 20 faster than solving LPs and 107,074 times faster than the monolithic approach (for the largest solvable instance by a commercial solver). The overall largest instance we solve, containing more than 79 million variables and constraints, converges in less than one minute using the calculation-based method. The modeling language GAMS and its latest features were used to efficiently implement all algorithms.
 
The paper appeared in Management Science, 63(6):2027-2048, 2017.