I need only the Matlab Code used in this research paper if possible.
Mixed Integer Linear Programming in Unit Commitment Aryan Agal Department of Energy Science and Energy Engineering India Institute of Technology, Bombay Email:
[email protected] Abstract—With the recent development of solution techniques, there is a trend to tackle the UC problem by using MILP approaches. This article goes over the unit commitment problem, the various constraints involved in it, and its mixed integer linear programming formulation. Index Terms—Unit Commitment, Mixed-Integer Linear Pro- gramming, High-Dimenional Constrained Optimization I. INTRODUCTION The Unit Commitment(UC) problem is a mathematical opti- mization problem, inherent to power generation, where a given set of electrical generators are to be operated in order to meet the load demand(the forecasted load demand, to be accurate), while optimizing towards an objective (which is generally economic). Besides achieving minimum total production cost, a generation schedule needs to satisfy a number of operating constraints. Generally, unit commitment is planned as per the availability of load forecasts: this may be hourly, and in recent times, every quarter-hourly. The unit commitment problem is generally a difficult one, since: (a) There are a large number of connected generators, (b) Generating units may be of many types, each coming with their own sets of constraints and different cost curves, (c) Generation is over a large geographical area and can affect the response of the electrical grid, and checking whether the load can be sustained and what the losses are requires highly complex power flow computations. The exact solution to the problem can be obtained by complete enumeration, which cannot be applied to realistic power systems due to its computational burden. Over the past five decades, multiple algorithms have been invented and/or applied to the UC problem.[1] These methods can be divided into three main categories: classical/deterministic, non- classical/stochastic approaches and hybrid techniques based on classical and non-classical approaches. In general, the UC problem falls into the category of large- scale and non-convex problems that are extremely difficult to solve in an accurate and efficient way.[2] Up to date, major approaches that used for solving UC problems include dy- namic programming, decomposition, nonlinear programming, mixed integer linear programming, and meta-heuristic-based methods.The major limitations on the convergence of these methods are the size of the problem or its discrete nature. Elements of the unit-commitment problem include a set of generating units with their cost/emission curves, a load profile to be satisfied, reliability constraints, financial constraints and time horizon along which decisions have to be made. The constraints that the decisions must meet include system requirements such as load balance and spinning reserve and unit limitations including generation and ramp-rate limits. II. MIXED INTEGER PROGRAMMING Mixed Integer Programming (MIP) or MILP is often posed in the form[3]: min x cx subject to: Ax ≤ B where x ∈ Zn × Rp It can be noted that objective function and all constraints are linear. Moreover, some variables are integers, some variables are continuous. In order to completely model the UC problem as an MILP one, multiple objectives and constraints must be altered. The min uptime and downtime constraints, as well as the stepped startup and shutdown costs must be linearized. The objective function itself, being often non-linear, must be linearized piecewise, and used. The common solution algorithm used for the UC problem is the Branch and Bound algorithm. It is a tree search algorithm, which follows three stages: (a)Branch: Pick a variable and divide the problem in two sub-problems at this variable. (e.g. if x ∈ {0, 1} solve the problem with x = 0 and the problem x = 1) (b)Bound: Solve the LP-relaxation to determine the best possible objective value for the node (c)Prune: Prune the branch of the tree (i.e.the tree will not develop further in this node) if either the sub-problem is infeasible OR the best achievable objective value is worse than a known optimum. The MATLAB R© algorithm for MILP is slightly advanced [4]; it builds upon the Branch and Bound technique. It starts by LP preprocessing i.e. reducing number of variables and constraints (and sometimes may detect infeasiblity). This is followed by solving the relaxed(non-integer) LP. Some in- teger preprocessing is done to tighten bounds and discard inequalities. LP is further tightened using Cut-Generation and heuristics are used to get integer-feasible solutions. Finally the branch and bound algorithm is used to process the problem systematically. The MILP formulation has gained interest recently because of the drastic improvement in numerical solution times of com- mercial MIP solvers [5]. The UC problem is highly suitable to be written as an MIP. It makes the problem easily and clearly accessible for adaptation. MIP has been put in use recently by ISOs in several markets including the PJM market(regional transmission organization in the United States). III. PROBLEM FORMULATION A. Notation N = Number of thermal units T = Number of time steps J = Number of segments of cost-curve ak,i = Coefficients of fuel cost function, for unit i fi(P t i ) = Fuel cost of unit i at time step t, with gener- ation output being P it uti = On/off status of unit i at time step t, (binary) pti = MW output of unit i at time step t pi = Minimum MW output of unit i pi = Maximum MW output of unit i Rui = MW output ramp-up limit of unit i Rdi = MW output ramp-down limit of unit i Uti = Minimum up time of unit i (hour) Dti = Minimum down time of unit i (hour) yti = Startup status at time step t of unit i (binary) zti = Shutdown status at time step t of unit i (binary) vti = Cold startup status at time step t of unit i (binary) Cu,i = Startup cost of unit i Cd,i = Shutdown cost of unit i Tcold,i = Cold startup hours for unit i Toff,i = Time since unit i is off fcold,i = Cold start cost for unit i fhot,i = Hot start cost for unit i Cd,i = Shutdown cost of unit i U0i = Initial Up-time status for unit i S0i = Initial Down-time status for unit i Dt = Total system demand at time step t Rt = Total system spinning reserve at time step t B. System constraints For a UC problem, we often have to look at the entire system to optimize commitment, and we must meet demands as well as the reserve and ensure that both of these are met at every time step. 1) Overall Load Balance: Tverall he total unit generation output must satisfy the system load demand requirement at each time step t, therefore N∑ i=1 pti = D t 2) Spinning Reserve: Spinning reserve is the term used to describe the total amount of generation available from all units synchronized (i.e., spinning) on the system, minus the present load and losses being supplied [6]. Units are required to N∑ i=1 uti(pi − pti) ≥ Rt Fig. 1: Piece wise Linear Approximation of a Convex Curve C. Unit Model The thermal generation model describes a thermal unit. Each individual plant is considered separately, and multiple constraints are applied. This section describes the MILP for- mulation for this model. 1) Cost during operation: Units are generally modeled as non-linear functions, often convex quadratic functions[7]. Since MILP requires requires a linear objective function, we take multiple pieces of the function and approximate them linearly. The figure given shows one such approximation. The unit cost function can be given by: fi(P i t ) = ai + biP i t + ci(P i t ) 2 To approximate as a two-segment linear function, we can use the following constraints: pti = p t i + 2∑ j=1 ptj,i pti = piu t i 0 ≤ pt1,i ≤ (pm,i − pi)uti 0 ≤ pt2,i ≤ (pi − pm,i)uti This approach can be extended further as number of pieces required. 2) Unit Maximum/Minimum Generation Limits: For each committed unit, the power generation pti should be within the generation limits of the unit, i.e. between its minimum and maximum possible generation. This can be expressed as: utipi ≤ pti ≤ utipi ∀i ∈ N, t ∈ 1...T 3) Unit Ramp Limits: Thermal units often are limited by the amount of stress that can be put to switch their power generation. This stress may be mechanical and/or thermal. This is formulated as: pt+1i − p t i ≤ Rui ∀i ∈ N, t ∈ 1...T pti − pt+1i ≤ Rdi ∀i ∈ N, t ∈ 1...T 4) Unit Startup and Shutdown Constraint: We may already have a unit on/off variable, but often that is not enough. To model constraints such as minimum up-time and startup/shut- down cost, we require two new variables, denoting the startup of the unit and shutdown of the unit. We use binary variables yti to denote startup and z t i to denote shutdown[8]. Now, a unit cannot startup and shutdown in the same time step. The startup constraints can be modelled as: uti − ut−1i = y t i − zti ∀i ∈ N, t ∈ 2...T yti + z t i ≤ 1 ∀i ∈ N, t ∈ 1...T 5) Unit Minimum-Up/Minimum-Down Time Constraints: Once a plant turns on, it must stay on for a certain number of hours before it can be turned off again. Similarly, once off it must stay off for a certain number of hours before it can be turned on again. These constraints can be modeled as: [9] ∀i ∈ N, t ∈ 2...T Minimum Uptime ζi∑ t=1 1− uti = 0, k+Uti−1∑ t=k uti ≥ Uti yki , ∀k = ζi + 1...T − Uti + 1 T∑ t=k uti − yti ≥ 0, ∀k = T − Uti + 2...T ζi = min{T, (Uti − U0i )ui,t=0} Minimum Downtime ηi∑ t=1 uti = 0, k+Dti−1∑ t=k 1− uti ≥ Dti zki , ∀k = ηi + 1...T −Dti + 1 T∑ t=k 1− uti − zti ≥ 0, ∀k = T − Uti + 2...T ηi = min{T, (Dti − S0i )[1− ui,t=0]} where Uti and Dti the corresponding minimum-up time and minimum-down time for the unit i, respectively. 6) Unit Hot/Cold Start Constraints: A recently shut-down plant generally is quicker and more efficient to start-up than a cooled one. This difference in cost can be modeled in the cost- function. We assume a step-function for the cost. If a plant is turned off within some time period, it only requires the cold start cost, else the hot-start cost. This is expressed below: StartupCost = { hotstartcost, if down-time ≤ cold start T coldstartcost, otherwise These constraints may be linearized.[10] To do so, we introduce an T toff,i variable. To determine number of off hours: T toff,i ≤M [1− yti ]