This repository contains the code to reproduce the results presented in the paper GCS-Q: Quantum-supported Graph Coalition Structure Generation, submitted to the The International Conference on Computational Science 2023 – Prague, Czechia.
We propose GCS-Q, a novel hybrid quantum-classical approach for solving the Coalition Structure Generation (CSG) problem for Induced Subgrapg Games (ISGs). In particular, the strategy is to follow a top-down approach and at each step explore an exponential number of possible next steps and choose the optimum greedily. The exploration of next steps and choosing the optimal can be formulated as a Quadratic Binary Combinatorial Optimization (QUBO) problem so that it is possible to leverage existing quantum techniques to solve efficiently. The algorithm can provide near optimal results in polynomial time.
Then we perform a comparative analysis in terms of time complexity between the proposed quantum algorithm and the most popular classical baselines. Furthermore, we consider standard benchmark distributions for coalition values to test the GCS-Q on small to medium-scale problem instances using the quantum annealing. We executed on a real quantum annealer device (Dwave).
Since GCS-Q algorithm is an approximate solver, an exact solver Improved Dynamic Programming (IDP) is used to get the optimal solutions.
Regarding the proposed top-down approach, the important difference in the experimental setting is with solving the optimal split sub-task in the pipeline of GCS-Q. It can be solved using brute force enumeration which takes
- Brute Force: uses classical computing to solve the optimal split problem by exhaustively searching all possible ways of dividing a set of agents into two.
- QUBO solver: uses classical computing to solve the optimal split problem by reformulating it into a min-cut problem and further to QUBO, finally solving the equivalent QUBO using Qiskit APIs.
- Quantum Annealing: uses the D-Wave quantum annealer to solve the optimal split problem.
The results reported in the paper are contained in the QA results directory. Furthermore, in the path ./optimal_split_problem, the notebook bipartite_as_mincut.ipynb contains code executing only the optimal split problem using the three methods mentioned above for Laplace and Normal distributions, and view the results from a generated file named bipartite_report_<seed_number>.txt.
The script Utils_CSG.py contains the helper functions in structuring the outputs and generating the reports. get_QUBO_coeffs() function converts the min-cut problem instance into linear and quadratic terms required for QUBO formulation.
The script Utils_Solvers.py contains the functions to use the APIs of dependencies like dimod for solving the input problem instances using the above three methods for finding the optimal split.
The script Experiments.py contains the configurations to set-up for starting the experiments.
The final report is generated by considering the best results in terms of two criteria: the best value for the optimization function and the best rank in terms of the probabilities generated for all possible binary strings.
There are three notebooks in this repository. Two of them help to collect the experimental results, namely:
-
Experiments.ipynb contains the source code for selecting the solvers and running the experiments to finally generate a .txt file containing the experimentally observed data like optimal coalition structure ($CS^$), value of the optimal coalition structure ($v(CS^)$), time to execute and approximation ratio compared to the
$v(CS^*)$ obtained from IDP. - plots.ipynb reads the file generated by the experiments and helps to generate plots illustrated in the paper.
- plot_theoretical_complexities.ipynb considers the theoretical time complexity of various classical solvers like Integer Partition (IP), Bi-directional Search Technique for Optimal Coalition Structure Generation with Minimal Overlapping (BOSS), Improved Dynamic Programming(IDP), BILP-Q, k-Graph Clustering (k-GC), Coalition Formation with Sparse Synergies (CFSS), Coalition-Link (C-Link), DyCE. The code generates a plot to show the order of growth in compleixties of all the algorithms along with GCS-Q as a function of the number of agents.
After having installed all the packages in the requirements.txt, a successful execution of the script will generate the output according to the following set of parameters.
The following are parameters to be set in the file Experiments.py before running the experiments:
- distributions: list of function names, currently having 'Normal' and 'Laplace'.
- n_agents: list of integers mentioning the number of agents considered for experiments.
- dwave_runs: number of runs for each instance on the dwave system.
- create_file: Boolean value, if True, a new directory is created for each distribution.
- seed: seed value for numpy to generate random numbers.
- dwave: Boolean value to specify whether using DWave for the running experiments.
- IDP_brute_force: Boolean value to specify whether using IDP exact solver for the running experiments.
- IDP_topdown_min_cut: Boolean value to specify whether to consider top-down approach and solving the optimal split using brute force technique.
- IDP_topdown_qubo: Boolean value to specify whether to consider top-down approach and solving the optimal split using QUBO solver from qiskit.
- IDP_min_cut_dwave_annealer: Boolean value to specify whether to consider top-down approach and solving the optimal split by accessing Dwave annealer via APIs.
For any issues or questions related to the code, open a new git issue or send a mail to [email protected] or [email protected].