An Improved Lagrangian Relaxation Algorithm for the Robust Generation Self-Scheduling Problem

The robust generation self-scheduling problem under electricity price uncertainty is usually solved by the commercial solver, which is limited in computation time and memory requirement. This paper proposes an improved Lagrangian relaxation algorithm for the robust generation self-scheduling problem where the quadratic fuel cost and the time-dependent exponential startup cost are considered. By using the optimal duality theory, the robust generation self-scheduling problem, which has a max-min structure, is reformulated as a minimization mixed integer nonlinear programming (MINLP) problem. Upon the reformulation, the Lagrangian relaxation algorithm is developed. To obtain a solvable relaxed problem, the variable splitting technique is introduced before the relaxation. The obtained relaxed problem is decomposed into a linear programming-type subproblem and multiple single-unit subproblems. Each single-unit subproblem is solved optimally by a two-stage backward dynamic programming procedure. The special cases of the problem are discussed and a two-stage algorithm is proposed. The proposed algorithms are tested on test cases of different sizes and the numerical results show that the algorithms can find near-optimal solutions in a reasonable time.