Towards Less Greedy Quantum Coalition Structure Generation in Induced Subgraph Games

Towards Less Greedy Quantum Coalition Structure Generation in Induced Subgraph Games

Abstract:

Switching to 100 % renewable energy production is one of the most important steps societies are currently taking in combating the climate crisis. This switch however requires new techniques for the management of power networks, such as their division into micro-grids containing sensible subsets of prosumers. Creating this division in an optimal manner is a challenging optimization problem which can be simplified to the Coalition Structure Generation problem in Induced Subgraph Games. This is a problem formulation in which one seeks to divide an undirected, fully-connected, weighted graph into a set of fully-connected subgraphs, in a manner that maximizes the sum over the weights of the edges contained in these subgraphs. In the last few years, several Quantum Annealing (QA)-based approaches have been proposed to solve this problem, the most recent of which is an efficient, but greedy algorithm called GCS-Q. In this thesis, we propose many different, less greedy QA-based approaches to solving the above-mentioned problem, to see if any of these algorithms can outperform GCS-Q in terms of solution quality. Testing these approaches on three different solvers – the QBSolv software, the D-Wave Advantage 4.1 quantum annealer and the QAOA algorithm using qiskit’s simulation software – we find that, while none of our suggested approaches can outperform the quantum state- of-the-art algorithm on current QA hardware, most of them do when using the QBSolv software. The best of these approaches is an algorithm we call 4-split iterative R-QUBO, which finds the optimum for all problem graphs in our dataset and scales quite favorably with the graph size in terms of runtime. Thus, we see this algorithm as a promising candidate for future research on quantum approaches for the problem in question.

Author:

Daniëlle Schuman

Advisors:

Jonas Nüßlein, David Bucher, Claudia Linnhoff-Popien

Student Thesis | Published May 2024 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors