I'm trying to partition a graph into k partitions with pre-defined sizes, so I'm using one weight per vertex and use the target weights to set the sizes. I'm using these options:

Name: graph.dat, #Vertices: 14412, #Edges: 1392146, #Parts: 78
Options ---------------------------------------------------------------------
ptype=rb, objtype=cut, ctype=shem, rtype=fm, iptype=grow
dbglvl=0, ufactor=1.001, minconn=NO, contig=NO, nooutput=NO
seed=6, niter=10, ncuts=1

And getting this output:

- Balance:
constraint #0: 1.141 out of 0.140
- Most overweight partition:
pid: 67, actual: 1042, desired: 913, ratio: 1.14.

If I understand correctly, this is imbalance of 1.14, which is much higher than the specified 1.001. I read on a different post on this forum that imbalance is a hard constraint, so I'm not sure why I'm getting such a high imbalance. When I change the random seed, I often get imbalance of even 1.62. Is there a way to enforce a particular max-imbalance?

Right now I'm thinking about doing a post-processing step to even out the partitions using a greedy heuristic, but I would think that such a heuristic would already be a part of Metis.

Is there a way to run Metis longer to get a better solution? For now, I'm thinking of running it N times with different seeds and picking the best partitioning based on imbalance.

Any thoughts on this?

Thank you!

RE: The balance is a hard

The balance is a hard constraint, however, Metis may fail to compute a balance partitioning if the weights of the vertices is highly variable. I presume this is a graph that has weights on the vertices. Can you confirm that a balanced solution is possible (e.g., given the vertex weights, can you do a simple bin-packing type of partitioning that will achieve the balance on 78-way partitioning)?