Local Search Methods for Min-Max Clearing Problem
Qiwei Sun, Toshiyuki Miyamoto, Shoichi Kitamura, Ayako Taniguchi-Matsuoka, Kento Naito, Kazuyuki Mori, Yoshio Izui · Transactions of the Institute of Systems Control and Information Engineers · 2022
In the ongoing power system reform in Japan, the division of transmission and distribution is separated from the former general electric utility and became a general power transmission and distribution business operator. After the reform, the power transmission and distribution business operators will procure reserve power from the reserve market. We have formulated the clearing problem in the reserve market as a 0-1 integer programming problem. This problem can be viewed as a Min-Max set multi-cover problem. Since the set covering problem belongs NP-hard, it is not easy to solve large-scale problems in practical time. In this paper, we propose a greedy solution and local search solution to the Min-Max set multi-cover problem and evaluate its performance by numerical experiments.