×

A stabilised scenario decomposition algorithm applied to stochastic unit commitment problems. (English) Zbl 1403.90528

Summary: In recent years the expansion of energy supplies from volatile renewable sources has triggered an increased interest in stochastic optimisation models for hydro-thermal unit commitment. Several studies have modelled this as a two-stage or multi-stage stochastic mixed-integer optimisation problem. Solving such problems directly is computationally intractable for large instances, and alternative approaches are required. In this paper, we use a Dantzig-Wolfe reformulation to decompose the stochastic problem by scenarios. We derive and implement a column generation method with dual stabilisation and novel primal and dual initialisation techniques. A fast, novel schedule combination heuristic is used to construct very good primal solutions, and numerical results show that knowing these from the start improves the convergence of the column generation method significantly. We test our method on a central scheduling model based on the British National Grid and illustrate that convergence to within 0.1% of optimality can be achieved quickly.

MSC:

90C11 Mixed integer programming
90C15 Stochastic programming
90C90 Applications of mathematical programming

Software:

CPLEX; AMPL

References:

[1] Briant, O.; Lemaréchal, C.; Meurdesoif, P.; Michel, S.; Perrot, N.; Vanderbeck, F., Comparison of bundle and classical column generation, Mathematical Programming, 113, 2, 299-344 (2008) · Zbl 1152.90005
[2] Carøe, C. C.; Schultz, R., A two-stage stochastic program for unit commitment under uncertainty in a hydro-thermal power system, Technical report SC 98-11 (1998), Konrad-Zuse-Zentrum für Informationstechnik
[3] Carøe, C. C.; Tind, J., L-shaped decomposition of two-stage stochastic programs with integer recourse, Mathematical Programming, 83, 1-3, 451-464 (1998) · Zbl 0920.90107
[4] Carrión, M.; Arroyo, J. M., A computationally efficient mixed-integer formulation for the thermal unit commitment problem, IEEE Transaction on Power Systems, 21, 3, 1371-1378 (2006)
[5] Cheung, K.; Gade, D.; Silva-Monroy, C.; Ryan, S. M.; Watson, J. P.; Wets, R. J.B., Toward scalable stochastic unit commitment part 2: Solver configuration and performance assessment, Energy Systems, 6, 3, 417-438 (2015)
[6] Fourer, R.; Gay, D. M.; Kernighan, B. W., AMPL - A modeling language for mathematical programming (2003), Brooks/Cole
[7] Gade, D.; Hackebeil, G.; Ryan, S. M.; Watson, J. P.; Wets, R. J.B.; Woodruff, D. L., Obtaining lower bounds from the progressive hedging algorithm for stochastic mixed-integer programs, Mathematical Programming, 157, 1, 47-67 (2016) · Zbl 1338.90282
[8] Ghaddar, B.; Naoum-Sawaya, J.; Kishimoto, A.; Taheri, N.; Eck, B., A Lagrangian decomposition approach for the pump scheduling problem in water networks, European Journal of Operational Research, 241, 2, 490-501 (2015) · Zbl 1339.90135
[9] Goez, J.; Luedtke, J.; Rajan, D.; Kalagnanam, J., Stochastic unit commitment problem, Technical Report RC24713 (W0812-119) (2008), IBM Research Division
[10] Gröwe-Kuska, N.; Römisch, W., Stochastic unit commitment in hydro-thermal power production planning, 605-624 (2002), Humboldt Universität Berlin
[11] Hechme-Doukopoulos, G.; Brignol-Charousset, S.; Malick, J.; Lemaréchal, C., The short-term electricity production management problem at EDF, Optima, 84, 2-6 (2010)
[12] Higle, J.; Rayco, B.; Sen, S., Stochastic scenario decomposition for multi-stage stochastic programs, IMA Journal of Management Mathematics, 21, 1, 39-66 (2009) · Zbl 1181.90205
[14] Jiang, R.; Guan, Y.; Watson, J.-P., Cutting planes for the multi-stage stochastic unit commitment problem, Technical Report SAND2012-9093J (2012), Sandia National Laboratories
[15] Klein Haneveld, W. K.; van der Vlerk, M. H., Stochastic integer programming: General models and algorithms, Annals of Operations Research, 85, 0, 39-57 (1999) · Zbl 0920.90110
[16] Krall, E.; Higgins, M.; O’Neill, R. P., RTO unit commitment test system, Technical Report AD10-12-002 (2012), Federal Energy Regulatory Commission (FERC)
[17] Lemaréchal, C., Lagrangian relaxation, Computational combinatorial optimization, 112-156 (2001), Springer · Zbl 1052.90065
[18] Lübbecke, M. E.; Desrosiers, J., Selected topics in column generation, Operations Research, 53, 6, 1007-1023 (2005) · Zbl 1165.90578
[19] Lubin, M.; Hall, J. A.J.; Petra, C. G.; Anitescu, M., Parallel distributed-memory simplex for large-scale stochastic LP problems, Computational Optimization and Applications, 55, 3, 571-596 (2013) · Zbl 1276.90044
[20] Lulli, G.; Sen, S., A branch-and-price algorithm for multistage stochastic integer programming with application to stochastic batch-sizing problems, Management Science, 50, 6, 786-796 (2004) · Zbl 1232.90314
[21] Nowak, M. P.; Römisch, W., Stochastic Lagrangian relaxation applied to power scheduling in a hydro-thermal system under uncertainty, Annals of Operations Research, 100, 1-4, 251-272 (2000) · Zbl 1017.90072
[22] Ogbe, E.; Li, X., A new cross decomposition method for stochastic mixed-integer linear programming, European Journal of Operational Research, 256, 2, 487-499 (2017) · Zbl 1394.90440
[23] Ostrowski, J.; Anjos, M. F.; Vannelli, A., Tight mixed integer linear programming formulations for the unit commitment problem, IEEE Transactions on Power Systems, 27, 1, 39-46 (2012)
[24] Papavasiliou, A.; Oren, S. S., Multiarea stochastic unit commitment for high wind penetration in a transmission constrained network, Operations Research, 61, 3, 578-592 (2013) · Zbl 1273.90035
[25] Papavasiliou, A.; Oren, S. S.; O’Neill, R. P., Reserve requirements for wind power integration: A scenario-based stochastic programming framework, IEEE Transactions on Power Systems, 26, 4, 2197-2206 (2011)
[26] Rajan, D.; Takriti, S., Minimum up/down polytopes of the unit commitment problem with start-up costs, Technical Report RC23628 (W0506-050) (2005), IBM Research Division
[27] Rockafellar, R. T.; Wets, R. J.B., Scenarios and policy aggregation in optimization under uncertainty, Mathematics of Operations Research, 16, 1, 119-147 (1991) · Zbl 0729.90067
[28] Sagastizábal, C., Divide to conquer: Decomposition methods for energy optimization, Mathematical Programming, 134, 1, 187-222 (2012) · Zbl 1254.90238
[29] Schulze, T., Stochastic programming for hydro-thermal unit commitment (2015), The University of Edinburgh, Ph.D. thesis
[30] Schulze, T.; McKinnon, K., The value of stochastic programming in day-ahead and intraday generation unit commitment, Energy, 101, 1, 592-605 (2016)
[31] Shiina, T.; Birge, J. R., Stochastic unit commitment problem, International Transactions in Operational Research, 11, 1, 19-32 (2004) · Zbl 1057.90039
[32] Takriti, S.; Birge, J. R., Using integer programming to refine Lagrangian-based unit commitment solutions, IEEE Transactions on Power Systems, 15, 1, 151-156 (2000)
[33] Takriti, S.; Birge, J. R.; Long, E., A stochastic model for the unit commitment problem, IEEE Transactions on Power Systems, 11, 3, 1497-1508 (1996)
[34] Vanderbeck, F., Implementing mixed integer column generation, Column generation (2005), Springer, 331-158 · Zbl 1246.90108
[35] Vanderbeck, F.; Savelsbergh, M. W.P., A generic view of Dantzig-Wolfe decomposition in mixed integer programming, Operations Research Letters, 34, 3, 296-306 (2006) · Zbl 1109.90062
[36] Wang, S. J.; Shahidehpour, S. M.; Kirschen, D. S.; Mokhtari, S.; Irisarri, G. D., Short-term generation scheduling with transmission and environmental constraints using an augmented Lagrangian relaxation, IEEE Transactions on Power Systems, 10, 3, 1294-1301 (1995)
[37] Watson, J. P.; Woodruff, D., Progressive hedging innovations for a class of stochastic resource allocation problems, Computational Management Science, 8, 4, 355-370 (2011) · Zbl 1225.91032
[38] Zheng, Q. P.; Wang, J.; Pardalos, P. M.; Guan, Y., A decomposition approach to the two-stage stochastic unit commitment problem, Annals of Operations Research, 210, 1, 387-410 (2013) · Zbl 1284.90114
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.