This repository contains the code to reproduce the results presented in the paper QuACS : Variational Quantum Algorithm for Coalition Structure Generation in Induced Subgraph Games, published in the 20th ACM International Conference on Computing Frontiers 2023 – Bologna, Italy.
We propose QuACS, 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 algorithm on small to medium-scale problem instances using the quantum simulators available in Qiskit.
Since QuACS algorithm is an approximate solver, an exact solver Improved Dynamic Programming (IDP) is also implemented to find 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 QuACS. 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 Simulator: uses the aer_simulator provided in qiskit.
The results reported in the paper are contained in the text format in the Reports directory. The notebook generatePlots.ipynb can be used to parse the report text files and visualize the results. The plots are also saved and available in the QAOA results directory.
The scripts utils.py,Utils_Solvers.py, min_cut_solvers.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 Experiments.py contains the configurations to set-up for running the experiments.
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.
- generatePlots.ipynb reads the file generated by the experiments and helps to generate plots illustrated in the paper.
- Experiments_OptimalSplit.ipynb contains the source code for selecting the solvers and running the experiments for the exponentially complex sub-task of finding the optimal split as a min-cut problem.
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.
- p: number of QAOA layers for solving the min-cut problem.
- seed: seed value for numpy to generate random numbers.
- 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 classically.
- IDP_gate_based: Boolean value to specify whether to consider top-down approach and solving the optimal split using qiskit's aer_simulator.
For any issues or questions related to the code, open a new git issue or send a mail to [email protected] or [email protected].