Exploiting Symmetry in the Generation Expansion Planning Problem to Accelerate Crossover

Abstract

Computational efficiency is essential for large-scale mathematical optimisation problems, such as the generation expansion planning problem, to be practically applicable. In linear programming solvers, crossover is frequently a bottleneck when solving optimisation problems. This study aims at determining why crossover is a bottleneck in solving the generation expansion planning problem and deriving a method which obtains an optimal solution faster. Symmetry was found to be disrupting crossover, causing its runtime to significantly increase. However, the preceding barrier method benefit from the symmetry handling of the solver. An alternative approach using problem-specific knowledge to reduce symmetry before serving the model to a solver was proposed. The key to the efficiency of this method is using the information of how symmetries are reduced when retrieving the solution to the original problem. The approach was applied to two types of symmetry we identified in the generation expansion planning problem, leading to a significant speed-up of the crossover phase and total runtime for the algorithm resolving a formulation symmetry, but a longer runtime for the method resolving a more practically available non-formulation symmetry. However, the latter was faster in a couple of cases and has many directions for future improvements. The results of this research, thus, demonstrate that domain knowledge of linear programming problems can be applied to reduce symmetry that state-of-the-art solvers cannot detect and to more efficiently obtain an optimal solution than traditional crossover.