Short-term Hydro-thermal Coordination By Lagrangian Relaxation: A New Algorithm for the Solution of the Dual Problem


For decades, researchers have been studying the unit commitment problem in electrical power generation. To solve this complex, large scale and constrained optimization (primal) problem in a direct manner is not a feasible approach, which is where Lagrangian relaxation comes in as the answer. The dual Lagrangian problem translates a relaxed problem approach, that indirectly leads to solutions of the original (primal) problem. In the coordination problem, a decomposition takes place where the global solution is achieved by coordinating between the respective subproblems solutions. This dual problem is solved iteratively, and Lagrange multipliers are updated between each iteration using subgradient methods. To tackle, time-consuming tuning tasks  or user related experience, a new adaptative algorithm, is proposed to better adjust the step-size used to update Lagrange multipliers, i.e., avoid the need to pre-select  a set of parameters. A results comparison against a traditionally employed step-size update mechanism, showed that the adaptive algorithm manages to obtain improved performances in terms of the targeted primal problem.

Keywords: Hydro-Thermal coordination, Lagrangian relaxation, Lagrangian dual problem, Lagrange multipliers, Subgradient methods

[1] F. Y. K. Takigawa, E. C. Finardi, and E. L. da Silva, “A decomposition strategy to solve the Short- Term Hydrothermal Scheduling based on Lagrangian Relaxation,” in 2010 IEEE/PES Transmission and Distribution Conference and Exposition: Latin America (T&D-LA), 2010, pp. 681–688.

[2] H. Ye, Q. Zhai, Y. Ge, and H. Wu, “A Revised Subgradient Method for Solving the Dual Problem of Hydrothermal Scheduling,” in 2011 Asia-Pacific Power and Energy Engineering Conference, 2011, pp. 1–6.

[3] Q. Zhai and H. Wu, “Several notes on Lagrangian Relaxation for unit commitment,” in Proceedings of the 29th Chinese Control Conference, 2010, pp. 1848–1853.

[4] T. T. Nguyen and D. N. Vo, “Multi-Objective Short-Term Fixed Head Hydrothermal Scheduling Using Augmented Lagrange Hopfield Network,” J. Electr. Eng. Technol., vol. 9, no. 6, pp. 1882–1890, Nov. 2014.

[5] L. A. F. M. Ferreira et al., “Short-term resource scheduling in multi-area hydrothermal power systems,”Int. J. Electr. Power Energy Syst., vol. 11, no. 3, pp. 200–212, Jul. 1989.

[6] Ü. Başaran Filik and M. Kurban, “Solving Unit Commitment Problem Using Modified Subgradient Method Combined with Simulated Annealing Algorithm,” Math. Probl. Eng., vol. 2010, pp. 1–15, Jul. 2010.

[7] J. A. Marmolejo-Saucedo and R. Rodríguez-Aguilar, “A proposed method for design of test cases for economic analysis in power systems,” J. Appl. Res. Technol., vol. 13, no. 3, pp. 428–434, 2015.

[8] A. L. Diniz, C. Sagastizabal, and M. E. P. Maceira, “Assessment of Lagrangian Relaxation with Variable Splitting for Hydrothermal Scheduling,” in 2007 IEEE Power Engineering Society General Meeting, 2007, pp. 1–8.

[9] P. K. Singhal, “Generation scheduling methodology for thermal units using lagrangian Relaxation,” in 2011 Nirma University International Conference on Engineering, 2011, pp. 1–6.

[10] C. J. Lopez-Salgado, O. Ano, and D. M. Ojeda-Esteybar, “Hydrothermal scheduling with variable head hydroelectric plants: Proposed strategies using benders decomposition and outer approximation,” in 2016 IEEE Power and Energy Conference at Illinois (PECI), 2016, pp. 1–8.

[11] R. N. Rodrigues, E. L. da Silva, E. C. Finardi, and F. Y. K. Takigawa, “Solving the Short-Term Scheduling Problem of Hydrothermal Systems via Lagrangian Relaxation and Augmented Lagrangian,” Math. Probl. Eng., vol. 2012, pp. 1–18, Feb. 2012.

[12] R. Kumar, V. Garg, and B. Lal, “A Review Paper on Hydro-Thermal Scheduling,” Int. J. Emerg. Technol. Comput. Appl. Sci., vol. 5, no. 5, pp. 522–526, 2013.

[13] C. Beltran and F. J. Heredia, “Short-Term Hydrothermal Coordination by Augmented Lagrangean Relaxation: a new Multiplier Updating,” in IX Congreso Latino-Iberoamericano de Investigación Operativa, 1998, pp. 1–6.

[14] E. Gil and J. Araya, “Short-term Hydrothermal Generation Scheduling Using a Parallelized Stochastic Mixed-integer Linear Programming Algorithm,” Energy Procedia, vol. 87, pp. 77–84, 2016.

[15] S. J. P. S. Mariano, J. P. S. Catalão, V. M. F. Mendes, and L. A. F. M. Ferreira, “Optimising power generation efficiency for head-sensitive cascaded reservoirs in a competitive electricity market,” Int. J. Electr. Power Energy Syst., vol. 30, no. 2, pp. 125–133, 2008.

[16] M. Basu, “Hopfield neural networks for optimal scheduling of fixed head hydrothermal power systems,” Electr. Power Syst. Res., vol. 64, no. 1, pp. 11–15, Jan. 2003.

[17] T. T. Nguyen and D. N. Vo, “Modified cuckoo search algorithm for short-term hydrothermal scheduling,”Int. J. Electr. Power Energy Syst., vol. 65, pp. 271–281, 2015.

[18] M. Basu, “Improved differential evolution for short-term hydrothermal scheduling,” Int. J. Electr. Power Energy Syst., vol. 58, pp. 91–100, Jun. 2014.

[19] H. Zhang, J. Zhou, Y. Zhang, Y. Lu, and Y. Wang, “Culture belief based multi-objective hybrid differential evolutionary algorithm in short term hydrothermal scheduling,” Energy Convers. Manag., vol. 65, pp. 173–184, 2013.

[20] I. A. Farhat and M. E. El-Hawary, “Short-term hydro-thermal scheduling using an improved bacterial foraging algorithm,” in 2009 IEEE Electrical Power & Energy Conference (EPEC), 2009, pp. 1–5.

[21] S. Padmini, R. Jegatheesan, and D. F. Thayyil, “A Novel Method for Solving Multi- Objective Hydrothermal Unit Commitment and Sheduling for GENCO Using Hybrid LREP Technique,” Procedia Comput. Sci., vol. 57, pp. 258–268, 2015.

[22] C. Nayak and C. C. A. Rajan, “An evolutionary programming embedded Tabu search method for hydro- thermal scheduling with cooling banking constraints,” J. Eng. Technol. Res., vol. 5, no. 2, pp. 21–32, Feb. 2013.

[23] S. Ruiic, “Optimal Distance Method for Lagrangian Mulitpliers Updating in Short-Term Hydro-Thermal Coordination - Power Systems, IEEE Transactions on,” vol. 13, no. 4, pp. 1439–1444, 1998.