Lagrangian relaxation and its application to the unit-commitment-economic-dispatch problem

This study is concerned with the optimal scheduling of an electricity power system consisting of both hydro and thermal units. Using Lagrangian relaxation, the original (primal) problem may be written in a dual formulation; the problem then admits decomposition into more tractable sub-problems. Furthermore, the primal solution can be approximated closely by the dual solution, by using the duality gap as a termination criterion. A heuristic has been used to construct nearly optimal solutions to the primal problem based on the information provided by the dual problem. This paper highlights three main points: improved computational times, the economic significance of the Lagrange multipliers, and the implicit parallelism of this algorithm.