Unit commitment by structure based solution and efficient lagrangian relaxation

Lagrangian relaxation (LR) is one of the most promising approaches for solving power system unit commitment (UC) problems by means of decomposition. There are several technical challenges in developing an effective LR solution. The first is to devise an efficient dual optimization procedure. The second is to have a quick and reliable procedure for removing residual violations in the relaxed constraints. The third is to make the solution algorithm less dependent of problem domain knowledge to improve solution portability. This paper presents a general algorithm that depends only on the formal structure of the problem formulation and assumes no specific knowledge in the problem domain. The proposed algorithm has been tested on real unit commitment problems with as many as 50,000 integer variables and has consistently produced good solutions with very limited number of iterations. In addition to being very efficient, the proposed algorithm is also seen to be robust under parametric perturbations.