Cut-based matheuristic algorithms to detect tacit collusion in deregulated electricity markets

In deregulated electricity markets, the trading mechanism aims at maintaining competition among generator companies to enable just and affordable electricity prices. The relationship between generators and Independent System Operator (ISO) can be considered as a Stackelberg game formulated as a bi-level optimization problem where each generator maximizes its profit at the upper level, while ISO minimizes the cost of generation for market clearing at the lower level. Theoretically, the market is considered to be in a Nash equilibrium state under an ideal level of competition. Yet, generators could collude tacitly to obtain larger profits than they would have obtained from the largest payoff in a Nash equilibrium. In order to detect such collusions, we consider a non-linear bi-level problem formulation. The original bi-level formulation is reformulated using two alternative mixed integer linear programming formulations utilizing the linear programming property of the lower level and various linearization methods. Besides a total enumaration algorithm (based on a trivial but computationally expensive method) to detect collusions, we develop matheuristic algorithms relying on adding cuts, identification of Nash equilibrium state, partial enumeration methods and their combinations. The performance of the algorithms is compared with each other based on their capacity in identifying collusive states and the required computational effort.