Home / files / instances / BCPk

Balanced Connected k-Partition Problem (BCPk) - Instances

Instance Set

This page contains instances for the Balanced Connected k-Partition Problem (BCPk) used in Miyazawa, Moura, Ota & Wakabayashi [1]. These instances were generated according to the process described in [1]. Please, cite [1] if you use them.

• BCPk Small Grid Instances (up to 15x15): bcpk_grids_small (274 kB)
• BCPk Medium Grid Instances (up to 180x180): bcpk_grids_medium (39 MB)
• BCPk Large Grid Instances (greater than 210x210): bcpk_grids_large (41 MB)
• BCPk Random Instances: bcpk_random (3 MB)
• BCPk Real-World (Maps) Instances: bcpk_real (193 kB)

Instance Format

In order to understand the instance format, let us look at the file unicamp_624_901.in. The file begins with the following lines.

nnodes nedges type
624 901 graph

Which indicates that this is a graph with 624 nodes and 901 edges. Next, we see the following lines.

nodename posx posy weight
0 -47.0630772 -22.8241024 108
...
623 -47.062253049999995 -22.8252087 74

As one should expect, these lines indicates the properties of each vertex in the graph. The vertex with id 623, for example, has position (-47.062253049999995, -22.8252087) in the xy-plane and a weight of 74. The position of the vertices are not used by our algorithms, we just use it for visualization purposes. Finally, the file describes the edges in the graph.

endpoint1 endpoint2
0 552
...
613 614

Each of these lines describe an edge of the graph. In other words, this graph has an edge connecting vertices with ids 0 and 552. It also has an edge connecting vertices with ids 613 and 614.

References

• [1] Miyazawa F.K., Moura P.F.S., Ota M.J., Wakabayashi Y. (2021) Partitioning a graph into balanced connected classes: Formulations, separation and experiments. European Journal of Operational Research, 293, 826-836. https://doi.org/10.1016/j.ejor.2020.12.059