Minimum Up/Down Polytopes of the Unit Commitment Problem with Start-Up Costs

In this paper, we focus on an important application from the electric power industry, namely the unit commitment problem. It is the problem of scheduling a set of electric-power generators in response to future demand so that the generation cost is minimized. The generators may vary in terms of cost, lead time, and generating capacity. For a survey on the unit commitment problem and relevant literature, we refer the reader to Hobbs et al. (2001). The main results in this paper were also independently developed by Malkin and Wolsey (2004).

In the unit commitment problem, the resources are generators, and it is assumed that the demand at any period is known. There are usually three components to the cost: variable cost of production, fixed cost, and start-up costs. Furthermore, each generator has an operating range within which it must operate.

In this problem, each generator i has a minimum up time (Li) and a minimum down time (li). Thus, if the generator is started up in time t, then it must remain on for the next Li - 1 time periods (and similarly when shut down). These conditions are quite critical, and is one of the main reasons why these problems are hard to solve as mixed-integer programs. Using binary variables uit (where ) to indicate whether generator i is on, these constraints are modeled using the minimum up/down constraints in Takriti et al. (2000).

In Lee et al. (2004), the authors study the polytope of a relaxation of the unit commitment problem. In particular, they focus on the polytope of the minimum up/down constraints. This polytope can also be thought of as the projection of the unit commitment problem on the space of the u variables. They successfully characterize the convex hull of this relaxation (PT (L; l)) by developing a class of inequalities, which they call the alternating up/down inequalities. The authors show that these inequalities provide a complete description of the polyhedron, and also present a linear time separation algorithm. The authors present no computational study; however, by completely characterizing conv(PT (L; l)), they suggest the applicability of branch-and-cut techniques for solving the unit commitment problem. In this paper, we are interested in an extension of the unit commitment problem studied in Lee et al. (2004). In particular, we study the case where each generator also has start-up and shut-down costs. Thus, we need additional binary variables (v). We define binary variable vit to indicate whether a generator i is started up in period t; thus vit = 1 if and only if uit - uit-1 = 1. We wish to understand how the polytope of the minimum up/down constraints changes in the presence of these additional variables. In other words, we focus on the projection on the space of both u and v variables. We refer to this projection as CT (L; l). Naturally, this is a stronger relaxation to the unit commitment problem with respect to the extended variable formulation.

In Section 2, we present turn on/off inequalities (much smaller in size than the alternating up/down inequalities) that are facets to conv(CT (L; l). In fact, we show that these inequalities completely define conv(CT (L; l)) along with some trivial inequalities1. Thus, these inequalities dominate the alternating up/down inequalities on conv(CT (L; l)). We also show that PT (L; l) is the projection of CT (L; l) on the space of the u variables.

In Section 3, we incorporate the turn on/off inequalities in a branch-and-cut framework to solve real-world instances of the unit commitment problem, and discuss the computational results. Finally, in Section 4 we conclude by summarizing our contributions and discussing future directions for research.

By: Deepak Rajan; Samer Takriti

Published in: RC23628 in 2005


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .