Short-Term Scheduling of Thermal-Electric Generators Using Lagrangian Relaxation

This paper presents an expanded formulation of the unit commitment problem in which hundreds of thermal-electric generators must be scheduled on an hourly basis, for up to 7 days at a time. The underlying model incorporates the full set of costs and constraints including setup, production, ramping, and operational status, and takes the form of a mixed integer nonlinear control problem. Lagrangian relaxation is used to disaggregate the model by generator into separate subproblems which are then solved with a nested dynamic program. The strength of the methodology lies partially in its ability to construct good feasible solutions from information provided by the dual. Thus, the need for branch-and-bound is eliminated. In addition, the inclusion of the ramping constraint provides new insight into the limitations of current techniques. Computational experience with the proposed algorithm indicates that problems containing up to 100 units and 48 time periods can be readily solved in reasonable times. Duality gaps of less than 1% were achieved in all cases.