Lower bounds for Sparse Graph Partitioning

Graph Partitioning or Clustering Problem (GPP) has increasing applications in many domains like complex networks, data analysis, ...
The graphs in these applications usually have a large number of nodes but very sparse. Due to this characteristic,
heuristics are preferred to exact algorithms for solving GPP.
As those heuristics offer no performance guarantee, it is interesting if one can quickly compute good lower bounds for GPP
and use them for asserting the quality of heuristic solutions. The aim of this project is to experiment the computation of
such lower bounds based on linear programming models developed by our team (V.H. Nguyen and M. Minoux).
The project consists of the following tasks:
- build a library of large scale and sparse instances of GPP
- implement solutions for linear programming models using Gurobi and Networkx,
- report and compare results for all instances over the different models.