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 (Lⁱ) and a minimum down time (lⁱ). Thus, if the generator is started up in time t, then it must remain on for the next Lⁱ - 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 uⁱ_t (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 (P_T (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(P_T (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 vⁱ_t to indicate whether a generator i is started up in period t; thus vⁱ_t = 1 if and only if uⁱ_t - uⁱ_t-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 C_T (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(C_T (L; l). In fact, we show that these inequalities completely define conv(C_T (L; l)) along with some trivial inequalities1. Thus, these inequalities dominate the alternating up/down inequalities on conv(C_T (L; l)). We also show that P_T (L; l) is the projection of C_T (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.