Fix edge cases in unconstrained LP, rebalancer and FM

[N-Maas]

This fixes:

• An issue in unconstrained LP where the rollback assumed that rebalancing always succeeds
• Issues related to the bestOfThree function used by the rebalancer and FM to update move priorities. The problem is that bestOfThree does not work if some of the three blocks are overloaded. If all are overloaded, it could even cause the rebalancer to drop the node completely and thus not rebalancing correctly. For unconstrained FM and the rebalancer, this is solved with a fallback that considers all blocks (which cannot happen too often since the load increases monotonically in these cases). For constrained FM the block weight can fluctuate, thus the new implementation just ignores the balance constraint when updating priorities (balance is ensured when pulling the move from the queue)

Specifically, the combination of the unconstrained LP and rebalancer bug could result in a pathological case with much worse result. Almost all of the improvement comes from fixing this case (red -> blue), as shown here:

The benchmark set used here contains roughly 50-50 regular and irregular graphs, k is in {32, 64, 128, 256} (as small k are not affected).

On their own, the adjustments to rebalancer and FM bring a tiny improvement (blue -> orange), which is more in the order of statistical noise. I tested two variants for the rebalancer and FM as discussed with @larsgottesbueren and used the one with a tiny bit better results.

Running time seems unaffected.

[codecov[bot]]

Codecov Report

Merging #166 (e2eb97e) into master (b93c770) will increase coverage by 0.11%. The diff coverage is 100.00%.

:exclamation: Current head e2eb97e differs from pull request most recent head f95ab5b. Consider uploading reports for the commit f95ab5b to get more accurate results

@@            Coverage Diff             @@
##           master     #166      +/-   ##
==========================================
+ Coverage   78.89%   79.01%   +0.11%     
==========================================
  Files         202      202              
  Lines       19606    19610       +4     
  Branches     7962     8039      +77     
==========================================
+ Hits        15469    15495      +26     
+ Misses       4137     4115      -22     

Files	Coverage Δ
...partition/refinement/fm/localized_kway_fm_core.cpp	92.12% <100.00%> (ø)
...finement/fm/strategies/local_gain_cache_strategy.h	98.92% <100.00%> (-1.08%)	:arrow_down:
...ement/fm/strategies/local_unconstrained_strategy.h	96.55% <100.00%> (+0.02%)	:arrow_up:
...nt/label_propagation/label_propagation_refiner.cpp	89.83% <100.00%> (+4.85%)	:arrow_up:
...ment/label_propagation/label_propagation_refiner.h	85.36% <ø> (ø)
...ion/refinement/rebalancing/advanced_rebalancer.cpp	95.89% <100.00%> (-1.12%)	:arrow_down:

... and 9 files with indirect coverage changes

:mega: Codecov offers a browser extension for seamless coverage viewing on GitHub. Try it in Chrome or Firefox today!