یک روش جدید مبتنی بر MILP برای واحد تعهد در برنامه ریزی تولید قدرت

This paper presents a complete, quadratic programming formulation of the standard thermal unit commitment problem in power generation planning, together with a novel iterative optimisation algorithm for its solution. The algorithm, based on a mixed-integer formulation of the problem, considers piecewise linear approximations of the quadratic fuel cost function that are dynamically updated in an iterative way, converging to the optimum; this avoids the requirement of resorting to quadratic programming, making the solution process much quicker. From extensive computational tests on a broad set of benchmark instances of this problem, the algorithm was found to be flexible and capable of easily incorporating different problem constraints. Indeed, it is able to tackle ramp constraints, which although very important in practice were rarely considered in previous publications. Most importantly, optimal solutions were obtained for several well-known benchmark instances, including instances of practical relevance, that are not yet known to have been solved to optimality. Computational experiments and their results showed that the method proposed is both simple and extremely effective.

The Unit Commitment Problem (UCP) is the problem of deciding which power generating units must be committed/decommitted over a planning horizon (that lasts from 1 day to 2 weeks, generally split into periods of 1 h each). The production levels at which units must operate (pre-dispatch) must also be determined to optimise a given objective function. The committed units must usually satisfy the forecasted system load and reserve requirements, as well as a large set of technological constraints. This problem has great practical significance because the effectiveness of the schedules obtained has a strong economical impact on power generation companies. Due to this reason and to the problem’s high complexity (a prove that it is NP-hard has been given in [1]), it has received considerable research attention. Even after several decades of intensive study, it is still a rich and challenging topic of research. The proposed optimisation techniques for unit commitment encompass very different paradigms. These range from exact approaches and Lagrangian relaxation to rules of thumb or very elaborate heuristics and metaheuristics. In the past, the combinatorial nature of the problem and its multi-period characteristics have prevented exact approaches from being successful in practice: they resulted in highly inefficient algorithms that were only capable of solving small problem instances with virtually no practical interest. Heuristic techniques, such as those based on priority lists, did not totally succeed either, as they often lead to low quality solutions. Metaheuristics had very promising outcomes when they were first explored. The quality of their results was better than those achieved using well established techniques and good solutions were obtained very quickly. However, some drawbacks can be highlighted when metaheuristics are used. If one considers that the ultimate goal is to design a technique that can be accepted and used by a company, one major drawback of metaheuristics is their dependence on parameter tuning. Parameter tuning is time consuming and the complex tuning procedure requires profound knowledge of the algorithm implemented. Furthermore, accurate tuning is vital for algorithm performance. A second drawback is related to the lack of information that metaheuristics provide in terms of the quality of the solution (i.e., how far it is from the optimal solution). Some proposals have been presented to address these drawbacks; but this still remains an open line of research. An open issue is related to solution optimality and how it affects individual pay-offs in restructured markets where an independent system operator performs a centralised unit commitment. As stated in [2], only if problems are solved to optimality can one guarantee that units will receive their optimal dispatch and pay-off. Therefore, the design and development of optimisation techniques that provide optimal results to unit commitment problems are of crucial importance. The dramatic increase in the efficiency of mixed-integer programming (MIP) solvers has encouraged the thorough exploitation of their capabilities. Some research has already been directed towards defining of alternative, more efficient, mixed-integer linear programming (MILP) formulations of this problem (see e.g., [3]). Extensive surveys of different optimisation techniques and modelling issues are provided in [4], [5] and [6]. This paper proposes a MIP formulation for quadratic optimisation of the UCP, and also presents a method based on a linear formulation. The method has proven to be effective at solving instances of a practically relevant size. Instead of considering a quadratic representation of the fuel cost, the linear model considers a piecewise linear approximation of the function and updates it in an iterative process, by including additional pieces. Function updating is based on the solutions obtained in the previous iteration. The solution approach developed in this research was tested on several well-known test instances that were not known to have been solved to optimality. For each of them, the new approach iteratively converged to the optimal solution, even for the largest benchmark instances.

The main contributions of this paper are a complete formulation of the standard thermal unit commitment problem in quadratic programming and a novel and efficient methodology for approximating the quadratic cost of electricity generating units, with an iterative method that uses a linear model, converging to the exact solution. Using this method we were able to solve all instances of a widely used benchmark testbed, for which to the best of our knowledge no optimum results were previously reported. The paper also establishes optimal solution for small instances of the quadratic model (with and without ramp constraints) showing that a simple method exploring the potential of current state-of-the-art solvers can tackle problems that were not previously solvable. This achievement is particularly relevant in markets were the independent system operator performs a centralised commitment and where there is a guarantee that units will receive their optimal dispatch and pay-off only when problems are solved to optimality. Previously proposed techniques for unit commitment could not, in general, guarantee that this goal was achieved as they were mostly based on (meta) heuristics. Prior approaches based on mixed-integer programming provided approximations, and did not seek for convergence to optimality. A computational analysis has shown that the iterative linear method is capable of reaching the optimum of the quadratic model, when it is known, using much less computational time than required for its quadratic programming solution. For large problem instances, where the quadratic model could not be solved directly in a reasonable time, the iterative linear algorithm has found the optimal solution. Similar conclusions could be drawn when ramp constraints are considered. The iterative linear algorithm was also capable of reaching the optimum for all of the instances. This is particularly important for instances with more than 20 units, for which the straightforward use of the quadratic programming solver was not successful. As future work, we plan to extend the algorithm in order to solve a broader set of models, for example, to include other electricity generating technologies in addition to thermal units. The approach used to approximate the quadratic cost can be applied to any convex function. In terms of practical applications, this is a feature that should be explored, as it may lead to a better model for the true cost function (instead of quadratic).