Preamble
Unit Commitment (UC) has a research history of more than 50 years. UC models being large-scale mixed-integer nonlinear optimization problems solution approaches always have been inspired by ideas from different subdisciplines of optimization, with permanently adjusting “large-scale” to bigger and bigger numbers. In recent years, the integration of UC into energy optimization models which, themselves, already are large-scale, e.g., power flow or uncertainty management in production and trading, became a focal research topic.
The Early Days
In their UC literature synopsis [14] from 1994, Sheble and Fahd review the first 25 years of the development and identify approaches some of which later became major pathways in algorithmic unit commitment. On the one hand, they address heuristics, such as Exhaustive Enumeration, Priority Lists, or Simulated Annealing, as well as mathematically rigorous methods from subdisciplines of optimization as there are Dynamic Programming, (Mixed-Integer) Linear Programming, Network Flows, and Lagrangian Methods. The computationally more demanding rigorous methods, on the other hand, yield provably optimal solutions or at least lower bounds allowing for gap estimates between objective function values of the best feasible solution found so far and lower bounds generated in the course of the algorithm.
Lagrangian Relaxation - as it was
In [14] the authors grant a “clear consensus presently tending toward the Lagrangian Relaxation (LR) over other methodologies”. Indeed, still today LR offers flexible possibilities for relaxing constraints complicating the model, however, at the cost of having to solve repeatedly “close cousins” to the relaxed problem. The key features of LR applied to UC have been and still are:
(i) relaxation of constraints inter-linking units, e.g., load coverage or reserve requirements, and arrival at single-unit subproblems,
(ii) addition of the relaxed constraints, together with Lagrange multipliers, to the objective, so that the resulting problem is easier to solve than the original,
(iii) solution of the convex, non- smooth Lagrangian dual whose objective-function value calculation benefits from reduction to solving single-unit subproblems and whose optimal value forms a lower bound to the optimal value of the UC problem,
(iv) application of Lagrangian heuristics to obtain “promising” feasible primal solutions from the results of the dual optimization.
Lagrangian Relaxation - as it is
Fueled by improved bundle-trust subgradient methods for the Lagrangian dual and by permanent progress in “off-the-shelve” mixed-integer linear programming (MILP) software, up to the advent of market deregulation, two basic aproaches developed which still today are widely used:
(i) LR, often in conjunction with heuristic methods for finding “promising” feasible solutions,
(ii) direct solution (by branch-and-bound) of MILP formulations of UC by “off-the-shelve” solvers.
Lagrangian Relaxation - as it will be
Rather than the transition to different time horizons, from short via medium to long-term, the new economic environment in the course of energy market deregulation poses research necessities and provides incentive to integrate UC and ED with load flow and uncertainty treatment, [5]. The latter is intended in the widest sense, from handling stochasticity to topics of mathematical equilibria in the context of power trading and bidding into power markets. In particular, this means to integrate UC into models which already are complex themselves.
Power Flow - Integrating UC and AC Load Flow
This was considered utopic throughout the “Early Days”, but now became possible by studying the quadratic nonconvex AC load flow equations from the viewpoint of semidefinite optimization. In [6] after relaxation of the rank condition the solution to the dual of the remaining convex model allows to retrieve a primal solution often meeting the relaxed rank condition, and thus enabling to solve nonconvex power flow optimization problems to global optimality.
Power Flow – DC Model and Ohmic Losses
The DC Load Flow Model provides a linear approximation of its AC counterpart by resorting to linear relations and avoiding variables in the space of complex numbers, see [3, 4]. The Ohmic Losses approximation, [12], provides the possibility to include power losses within the DC-approximation of an AC power system. Precise modeling of power losses turns out instrumental in congestion management when load dispatches or even commitments of units have to be revised to increase throughput of the grid under increased inflows of renewables.
Polyhedral Methods
Despite its success in combinatorial optimization, cutting plane methods based on polyhedral studies, either applied directly or enhancing branch-and-bound came to the fore in UC a bit more than 10 years ago, only. At this time, market deregulation enforced the need of solving UC in a competitive environment under incomplete information. In this way, solving UC problems became a subroutine in the treatment of more complex decision problems in electricity supply. Today, tight formulations for crucial model ingredients and for complete polytopes arising in UC are available. In particular, [7] give a best-possible formulation of minimum up and down times for power-generating units. [11] give an alternative formulation with additional binary variables. [17] extend this to handle maximum up and down times. [11] provide techniques for handling slow- and quick-start units (startup and shutdown power trajectories for slow-start units, and startup and shutdown capabilities for quick-start units)
Uncertainty
In the presence of uncertainty, UC either lives in a non-competitive or competitive environment. The former concerns the time before, the latter since deregulation of energy markets. Before deregulation load has been the dominating uncertainty prone entity, [15]. After deregulation UC-relevant sources of uncertainty have spread considerably: power input from renewables, power prices determined by bidding into power exchanges, competitors’ actions at electricity markets. Yet, UC is understood in a broader context than before. It rather is the scheduling of decentralized power supply with its small generating facilities than commitment of thermal let alone nuclear generation units. While the mathematical apparatus is fairly well developed for exogenous uncertainty, the situation is completely different for endogenous uncertainty, i.e., with decision dependent probability distributions. In case uncertainty is captured by probability measures, stochastic integer programming offers methodology for handling UC, both algorithmically and regarding structural understanding, [2, 13, 15].
Demand Side Management
The interaction of growing distributed generation, with increased consumer flexibility and volatility of the input of renewable energy require a demand side management with unit commitment in a focal role and without neglecting the remaining determinates of the generation system. The market is invited to provide incentives for market participants to engage in Demand Side Management. Vice versa, engagement of market participants must be carried out in rational manner which, in turn, brings to the fore research at the interface of energy science and mathematics, with many open problems up to the present day. Last but not least, uncertainty of crucial model data remains a particular challenge.
References:
[1] Bertocchi, M.I., Consigli, G., Dempster, M.A.H. (Eds.) : Stochastic optimization methods in finance and energy, Springer, New York, 2011.
[2] Carøe, C.C.; Schultz R.: A Two-Stage Stochastic Program for Unit Commitment Under Uncertainty in a Hydro-Thermal Power System, ZIB Preprint 98-11, Konrad-Zuse-Zentrum fur Informationstechnik (ZIB) Berlin, 1998.
[3] Frank, S., Steponavice, I., Rebennack, S.: A primer on optimal power flow: A bibliographic survey - (i) formulations and deterministic methods, Energy Systems 3(2012), 221-258.
[4] Frank, S., Steponavice, I., Rebennack, S.: A primer on optimal power flow: A bibliographic survey - (ii) non-deterministic and hybrid methods, Energy Systems 3(2012), 259-289.
[5] Gabriel, S.A., Conejo, A.J., Fuller, J.D., Hobbs, B.F., Ruiz, C.: Complementarity Mdeli in Energy Markets, Springer, New York 2013.
[6] Lavaei, J., Low, S. H. : Zero duality gap in optimal power flow problem, IEEE Transactions on Power Systems 27(2011), 92-107.
[7] Lee, J., Leung, J., Margot, F.: Min-up/min-down polytopes, Discrete Optimization 1(2004), 7785.
[11] Morales-Espana, G., Gentile, C, Ramos, A.: Tight MIP formulations of the power-based unitcommitment problem, OR Spectrum (to appear 2015).
[12] Sanchez-Martin, P., Ramos, A.: . Modeling transmission ohmic losses in a stochastic bulk production cost model, Instituto de Investigacion Tecnologica, Universidad Pontificia Comillas, Madrid, 1997.
[13] Schultz, R.: Stochastic programming with integer variables, Mathematical Programming 97(2003), 285-309.
[14] Sheble, G.B., Fahd, G.N.: Unit commitment literature synopsis, IEEE Transactions on Power Systems 9(1994), 128-135.
[15] Takriti, S., Birge, J.R., Long, E.: A stochastic model for the unit commitment problem, IEEE Transactions on Power Systems 11(1996), 1497-1508.
[16] D. Rajan and S. Takriti. Minimum up/down polytopes of the unit commitment problem with start-up costs. Technical report, IBM Research Report RC23628, 2005.
[17] Queyranne, M., Wolsey, L.A. (2017). "Tight MIP formulations for bounded up/down times and interval-dependent start-ups". Mathematical Programming 164 129–155.
Contributors:
Dr Michael Diekerhof, RWTH Aachen University
Dr Mehdi Madani, Université catholique de Louvain
Prof. Jon Lee, University of Michigan