从NP-Hard到多项式时间算法的大规模机组组合近似线性规划:双重凸包模型

Unit commitment is one of the most important models for power system economics and operations. It usually takes the minimum cost as the objective function to meet the physical and security constraints of the power system operation. Mathematically, unit commitment is mixed-integer programming, which is essentially an NP-hard problem. As the scale of the system increases, the number of integer variables increases, and its computational complexity will also increase dramatically. In order to address the challenge of "the curse of dimensionality", this paper, based on the convex hull theory of single-unit, extended the convex hull of single-unit to multi-unit systems and established a convex hull model for large-scale unit commitment problems considering security constraints. Meanwhile, the strategy of dual convex hull embedded in multi-units commitment and the method of constructing a feasible solution were designed to solve the adaptability problem of units to convex hull and the non-0-1 solution problem of the optimal solution caused by the relaxation of the multi-units convex hull. Furthermore, two convex hulls were applied to multi-unit security-constrained unit commitment where the mixed-integer programming model was approximately transformed into linear programming, and integers were omitted. This idea has achieved an important breakthrough in the computational complexity from the NP-hard to the polynomial time, suitable for large-scale power system unit commitment models. Finally, simulation results of several provincial power systems show that the computational efficiency of the proposed method is 1~2 orders of magnitude higher than that of pure mixed-integer programming.