A Unit Commitment Algorithm With Relaxation-Based Neighborhood Search and Improved Relaxation Inducement

The computational efficiency of large-scale unit commitment (UC) is still a critical issue in power system and electricity market operations. To reduce the computation time of UC, relaxation-based neighborhood search (RBNS) and improved relaxation inducement (IRI) are proposed in this article. RBNS explores the neighborhood of the linear program (LP) relaxation optimal solution for a high-quality feasible solution. A new distance function, termed relaxation distance (RD), is proposed to measure the distance between the current solution and the tendency of the LP relaxation optimal solution. RBNS can substantially reduce the optimization space, and thus improve the efficiency. IRI has been developed to effectively induce binary variables towards the tendency of the relaxed solution. In contrast to a conventional relaxation inducement method, the binary variables are symmetrically and bi-directionally induced. The ratio between the inducing functions and the original objective function is optimized. IRI can induce more binary variables to integrality, and fewer binary variables need to be branched. Therefore, the size of the branch-and-bound tree can be reduced significantly. Modified IEEE-300 bus system and Polish 2746 bus system are used to demonstrate the effectiveness and performance of the proposed RBNS and IRI methods.