# What objective is satisfied first?

When partitionning a mesh (or a graph), there are 2 different objectives to satisfy: load balancing, and edge-cut. Which one of those 2 objectives is satisfied first. Or, are they satisfied both at the same time?

I have the following (very simple) graph :

adj : 0 2 3 5 6
adjncy : 1 2 0 0 3 2
vwgt : 66 66 21 21
adjwgt : 1 1 1 1 1 1

A very simple way to partition this graph would be to put one element that weights 66 with one element that weights 21, which would lead to a (87, 87) partition, which would be perfect. However, this also leads to a edge-cut of 2.

If I give this input to METIS, it gives me another partition, in which the two "66" elements are grouped together (and so are the two "21" elements), with an edge-cut of 1.

So, my question is : does Metis "search" for the best edge-cut AND THEN try to enhance the load balancing on each partition, OR does it search for the best load balancing AND THEN try to minimize the edge-cut, OR does it minimize the following objective [ abs(load1-load2) + edge_cut ]??

My interpretation of my results is that it first searches for the best edge_cut...

Benoît Schiltz

### RE: so, why?

So why in my very particular case is the load balancing so "misbalanced"? I mean, on my very little graph, the ratio between the less loaded part and the most loaded part is something like (21*2)/(66*2) = 1/3 ???? Isn't it surprising to have a result that is so bad while there is a much better solution with the same ratio that takes the value 1?

Also, on much larger meshes (or graphes), is it normal that for a 8-part partitioning, the ratio of the less loaded part and the most loaded part is something like 70%? It seems to me that is is a bit bad as a partitioning, no? The load-balancing is crucial for the soft I am developing, and that kind of misbalanced partition can lead to desastrous speed-ups in parallel computations (I develop a CFD-like time domain aeroacoustic simulation tool). Any ideas on how to improve the partitioning?

Benoît Schiltz

### RE: The load imbalance can

The load imbalance can happen for four reasons:
- metis has a loose 1.03% load imbalance that it considers to be good enough
- if the graph is too small, metis's heuristic balancing scheme tends to fail
- if you are over-partitioning a graph (nparts ~= nvtxs), the heuristics can
also fail.
- if the vertices have significantly different weights, then the recursive
decomposition approach that metis uses to compute the initial partitioning
may get it into a bad corner, in which balance cannot be achieved.

One way to try eliminate the last case is to formulate your partitioning problem
as a two-constraint problem whose second constraint will be to balance the number
of nodes between the partitions (the first constraint will be to balance the sum
of the vertex weights).

Is it possible to do that with Metis? Is it equivalent to : first partitioning with weights set to 1, and then give the result as input for a second partitioning with the "real" weights ?

How will I be able to deal with this two-constraint problem _and_ the minimization of the edge-cut?

The ideal scheme to me would be :
-achieve a "perfect" (1.03 seems ok to me) load-balancing
-have an edge-cut that is "reasonable"
(what I mean is that, clearly at this stage, the load balancing is much more important to me than the edge-cut, _but_ I cannot afford to affect a zero weight on the edges, because it would increase dramatically my communications between processes)

Any comment is welcome, thanks a lot...

Benoît schiltz

### RE: Metis has multi-constraint

Metis has multi-constraint partitioning routines that allow you to do that. Essentially, the two constraints are modeled as different vertex weights. Read the manual...

### RE: Metis actually enforces the

Metis actually enforces the load balance first and then optimizes the cut. The load balance is treated as a constraint.