The primary concern of electrical power system operators is having enough capacity to meet demands during their peak load periods. The limited amount of electric energy stored in the system reservoirs and base-loaded generators may not be sufficient to respond to high demands. Therefore, higher cost thermal generating units or purchased power are often used to make up for the supply shortage. The goal becomes to minimize the cost of operating and maintaining the thermal units over a planning horizon subject to meeting the demand for electricity.
In practice, experienced schedulers forecast the demand for each period of the planning horizon, which is usually one week or 168 hours. The demand is forecasted using the weather forecast and the data that have been already collected from similar periods in previous years. The forecasted demands are then used to find an optimum strategy, which determines which generators to switch on or off at each time period. Also, for each generator that is on, we need to determine the optimal generation level.
The previous optimization problem, known as the unit commitment problem [Muckstadt and Koenig 1977], is difficult since it involves binary decisions, i.e., an on/off decision must be made for each generator at each time period. There are also other operational constraints that make the unit commitment problem more complicated. For instance, when a unit is switched on it has to remain on for a certain number of periods. A similar constraint applies for the case when a unit is switched off: it has to be off for a certain number of periods. There are also upper and lower generating capacity bounds as well as start-up and shut-down costs associated with each generating unit. Each unit has a lead time: it takes a few hours after start-up to have a thermal unit on-line.
Some systems, such as the MEPCC system, also have a pumped storage hydro plant that further reduces the cost and enhances the reliability of the system. Since the marginal cost of generating electricity under low demands is smaller than that under high demands, costs can be reduced by storing energy generated during low-demand periods and using it in high-demand periods. Water is pumped into the reservoir during the night and over the weekend so that it can be used during the weekday afternoon periods. Having this stored energy in the reservoir protects the system against unexpected system shocks. However, pumped storage units make the problem more complex since they introduce interdependencies between time periods over the study horizon.
In general, the size of a unit commitment problem is relatively large. For instance, in the MEPCC system, there are more than one hundred thermal generating units and a pumped storage plant with six turbines. The resulting optimization problem is a mixed-integer program. Obtaining an exact solution for this problem may not be practical. It is solved approximately by relaxing the demand constraint and maximizing the resulting Lagrangian dual problem [Bertsekas, Lauer, Sandell, and Posbergh 1983]. A more detailed discussion can be found in Appendix A.