×

Multiperiod optimal planning of thermal generation using cross decomposition. (English) Zbl 1268.49037

J. Comput. Syst. Sci. Int. 50, No. 5, 793-804 (2011); translation from Izv. Ross. Akad. Nauk, Teor. Sist. Upr. 2011, No. 5, 109-120 (2011).
Summary: This work addresses the Multiperiod Optimal Planning of Thermal Generation (MOPTG). The model considered is based on a unit commitment problem that has multiperiod character and determines the start up and shut down schedules of thermal plants considering the line capacity limits of transmission and line losses. The mathematical model is stated in the form of a Mixed Integer Non Linear Problem (MINLP) with binary variables. To reduce the computational time caused by the large number of time periods and electric generation nodes we apply the Generalized Cross Decomposition [K. Holmberg, Math. Program., Ser. A 47, No. 2, 269–296 (1990; Zbl 0715.90078); T. J. Van Roy, Math. Program. 25, 46–63 (1983; Zbl 0505.90057)]. The latter exploits the structure of the problem to reduce solution time by decomposing the MOPTG into a primal subproblem, which is a Non Linear Problem (NLP), a dual subproblem, which is a MINLP, and a Mixed Integer Problem (MIP) called master problem. The approach is compared with Lagrangean relaxation [A. M. Geoffrion, Approach. Integer Program., Math. Program. Study 2, 82–114, (1974; Zbl 0395.90056 )] and generalized Benders decomposition [A. M: Geoffrion, J. Optimization Theory Appl. 10, 237–260 (1972; Zbl 0229.90024)]. To demonstrate the efficiency of the proposed decomposition strategy, we present numerical results obtained for three test systems. The computational experiments show the superiority of the cross decomposition approach.

MSC:

49M27 Decomposition methods
49N90 Applications of optimal control and differential games
90C11 Mixed integer programming

Software:

CONOPT; GAMS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] K. Holmberg, ”On the Convergence of the Cross Decomposition,” Math. Program. 47, 269–296 (1990). · Zbl 0715.90078 · doi:10.1007/BF01580863
[2] T.J. Van Roy, ”Cross Decomposition for Mixed Integer Programming,” Math Program. 25, 46–63 (1983). · Zbl 0505.90057 · doi:10.1007/BF02591718
[3] A.M. Geoffrion, ”Lagrangean Relaxation for Integer Programming,” Mathematical Programming Study 2, 82–114 (1974). · Zbl 0395.90056 · doi:10.1007/BFb0120690
[4] A.M. Geoffrion, ”Generalized Benders Decomposition,” J. Optim. Theory and Appl. 10(4), 237 (1972). · Zbl 0229.90024 · doi:10.1007/BF00934810
[5] A.J. Wood and B.F. Wollenberg, Power Generation, Operation and Control (Wiley, 1996)
[6] C.L. Tseng, On Power System Generation Unit Commitment Problems, Ph. D. Dissertation. UC Berkeley, December 1996.
[7] S. Ruzic and N. Rajakovic, ”A New Approach for Solving Extended Unit Commitment Problem,” IEEE Trans. PWR. 6(1), 269–275 (1991).
[8] S. Virmani, K. Imhof, and S. Mukherjee, ”Implement of a Lagrange Relaxation Based Unit Commitment Problem,” IEEE Trans. Power Systems. 4(4), 1373–1379 (1989). · doi:10.1109/59.41687
[9] J.F. Benders, ”Partitioning Procedures for Solving Mixed-variables Programming Problems,” Numerische Math. 4, 238–252 (1962). · Zbl 0109.38302 · doi:10.1007/BF01386316
[10] M. Pereira and L. Pinto, ”Application of Decomposition Techniques to the Mid and Short Term Scheduling of Hydrothermal Systems,” IEEE Trans. Power Apparatus and Systems 102(11), 3611–3618 (1983). · doi:10.1109/TPAS.1983.317709
[11] S. Granville, M. Pereira, G.B. Dantzig, et al., ”Mathematical Decomposition Techniques for Power Systems,” EPRI Tech. Rep. 1988, 2473–2476.
[12] A. Cohen and X. Yoshimura, ”A Branch and Bound Algorithm for Unit Commitment,” IEEE Trans. Power Apparatus and Systems 102(2), 444–451 (1983). · doi:10.1109/TPAS.1983.317714
[13] T. Dillon, K. Edwin, D. Kochs, et al., ”Integer Programming Approach to the Problem of Optimal Unit Commitment with Probabilistic Reserve Determination, IEEE Trans. Power Apparatus and Systems 97(6), 2154–2166 (1978). · doi:10.1109/TPAS.1978.354719
[14] A. Mantaway, Y. Abdel-Magid, and S. Selim, ”A Simulated Annealing Algorithm for Unit Commitment,” IEEE Trans. Power Systems 13, 197–204 (1998). · doi:10.1109/59.651636
[15] A. Mantaway, Y. Abdel-Magid, and S. Selim, ”Unit Commitment by Tabu Search,” IEEE Proc. Generation, Transmission and Distribution, 145(1), 56–54 (1998). · doi:10.1049/ip-gtd:19981681
[16] S. Kazarlis, A. Bakirtzis, and V. Petridis, ”A Genetic Algorithm Solution to the Unit Commitment Problem,” IEEE Trans. on Power Systems 11, 83–92 (1996). · doi:10.1109/59.485989
[17] Y. Hongchao and Dai. Wenzhi, ”Optimal Operational Planning of Steam Power Systems Using an IPSOSA algorithm,” J. Computer and Systems Sciences International 49(5), 750–756 (2010). · Zbl 1276.90088 · doi:10.1134/S1064230710050096
[18] A.J. Conejo, E. Castillo, R. Minguez, et al., Decomposition Techniques in Mathematical Programming (Springer, 2006).
[19] N. Alguacil and A. Conejo, ”Multiperiod Optimal Power Flow Using Benders Decomposition, IEEE Trans. Power Systems 15(1), 196–201 (2000). · doi:10.1109/59.852121
[20] P. Charman, P. Bhavaraju, and R. Billington, ”IEEE Reliability Test System,” IEEE Trans. Power Apparatus and Systems 98(6), 2047–2054 (1979).
[21] R. Christie, IEEE 118 Bus Test Case (College of Engineering, Electric Engineering, University of Washington, 1993). http://www.ee.washington.edu/research/pstca
[22] A. Brooke, D. Kendrick, and A. Meeraus, GAMS: A User’s Guide (The Scientific Press, 1998).
[23] P. Belloti, COUENNE: A User’s Manual, https://projects.coin-or.org/Couenne
[24] A.S. Drud, ”CONOPT–A Large Scale GRG Code,” ORSA J. Computing 6(2), 207–216 (1994). · Zbl 0806.90113 · doi:10.1287/ijoc.6.2.207
[25] A. Brooke, D. Kendrick, and A. Meeraus, GAMS/Cplex 12. User notes. GAMS Development Corporation. 2010.
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.