A comparison between mixed-integer linear programming and dynamic programming with state prediction as novelty for solving unit commitment

Recently, the increasing prevalence of renewable energies has faced the challenge of operating power supply systems to efficiently plan electricity generation on a daily basis, since renewable energies are generated intermittently and the decisions of the individual generation units are discrete. The Unit Commitment (UC) problem, which determines the dispatch of generation units, is one of the critical problems in the operation of power supply systems. A long list of formulation proposals have been made that claim to solve this problem. For this purpose, two established approaches, mixed-integer linear programming (MILP) and backward dynamic programming (DP), are used as basis for a deterministic single-generator unit with general convex cost function in this paper. The DP algorithm is enhanced by a so-called state prediction, which reduces the time to find the optimal solution. The proposed formulation is tested empirically on the basis of existing formulations at long term profit based UC instance derived from real data. Finally, the calculation results show that the derived approach significantly shortens the computation time, which confirms the effectiveness of state prediction. The comparison of the approaches shows that the DP algorithm with state prediction delivers a satisfying solution in significantly less time than DP and MILP. Furthermore, the given linearity of the dependence of the computation time on number of steps is a superior advantage of the DP strategy. This superiority becomes even more evident when the planning horizon extends over a longer period of time.

Automated summary

This paper addresses the Unit Commitment problem in power supply systems by using mixed-integer linear programming and backward dynamic programming. By enhancing the dynamic programming algorithm with state prediction, the proposed formulation significantly reduces computation time and delivers satisfactory solutions in a shorter time compared to other approaches. Additionally, the linear dependence of computation time on the number of steps is a key advantage of the dynamic programming strategy, especially for longer planning horizons.