VnBest hangs in some cases

[hhirtz]

Using num-part with the beta,0.2,0.2 distribution makes vnbest hang sometimes, esp with runs with more than 1000 weights.

[cedricchevalier19]

Can you obtain a reproducer ?

[hhirtz]

fn main() {
    use coupe::Partition;

    let weights = [
        504.51144132994574,
        504.51144132994574,
        3.4558264683830705e-14,
    ];
    let mut partition = [0, 1, 1];

    println!("partitioning");
    coupe::VnBest.partition(&mut partition, weights).unwrap();
}

imbalance 5.684341886080802e-14
   -> nearest weight is 3.4558264683830705e-14
    -> part_loads before [504.51144132994574, 504.5114413299458]
    -> part_loads after  [504.5114413299458, 504.51144132994574]

So we have a weight W strictly smaller than imbalance, but doesn't change the imbalance due to float imprecision.

[hhirtz]

Changing this line

https://github.com/LIHPC-Computational-Geometry/coupe/blob/1e9ecb63844b8a170535a0d81282b73f37556ee6/src/algorithms/vn/best.rs#L121

to

        if part_loads[underweight_part] + imbalance <= part_loads[underweight_part] + nearest_weight
            || nearest_weight.is_zero()

fixes the issue...