  The transition to 100% renewable energy requires new techniques for managing
energy networks, such as dividing them into sensible subsets of prosumers
called micro-grids. Doing so in an optimal manner is a difficult optimization
problem, as it can be abstracted to the Coalition Structure Generation problem
in Induced Subgraph Games, a NP-complete problem which requires dividing an
undirected, complete, weighted graph into subgraphs in a way that maximizes the
sum of their internal weights. Recently, Venkatesh et al. (arXiv:2212.11372)
published a Quantum Annealing (QA)-based iterative algorithm called GCS-Q,
which they claim to be the best currently existing solver for the problem in
terms of runtime complexity. As this algorithm makes the application of QA to
the problem seem promising, but is a greedy one, this work proposes several
less greedy QA-based approaches and investigates whether any of them can
outperform GCS-Q in terms of solution quality. While we find that this is not
the case yet on D-Wave hardware, most of them do when using the classical
QBSolv software as a solver. Especially an algorithm we call 4-split iterative
R-QUBO shows potential here, finding all optima in our dataset while scaling
favorably with the problem size in terms of runtime. Thus, it appears to be
interesting for future research on quantum approaches to the problem, assuming
QA hardware will become more noise-resilient over time.
