Evaluate Network Flow Solvers for SPEEDEX

[jonjove]

@gramseyer implemented a simplex algorithm to solve the network flow for SPEEDEX. It would be good to evaluate some other algorithms that might potentially perform better. One candidate is CS2 as described in "An Efficient Implementation of a Scaling Minimum-Cost Flow Algorithm" by A.V. Goldberg (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.258&rep=rep1&type=pdf).

We can modify https://github.com/scslab/speedex/blob/master/main/solver_comparison.cc to perform the benchmarks.

[mw221]

(@jonjove) Is there a publicly available version of the referenced paper?

[gramseyer]

I just pushed an update to that file integrating an implementation of network simplex. This seems to perform substantially better than I had expected.

To run it, you should be able to clone that repo and ./autogen.sh && ./configure && make solver_comparison. Usage is ./solver_comparison , and you can modify the experiment parameters within the file.

Fair warning, the repo uses a fair number of c++20 features, some of which don't seem to be supported by clang or which require slight modifications to use with clang (concepts, experiments with coroutines). I've been building with g++ 11.2.

Also fair warning is that the library implementing network simplex uses something in the standard library that was removed in c++20, so I had to edit ~10 lines of code (swapping allocator.construct for placement new, e.g.) to get it to build properly.

I haven't fully validated the correctness of the network simplex solver, but from just cursorily scanning the results, it seems to agree with my implementation of simplex and approximately agree with glpk (they're slightly different problem setups, so they won't 100% agree with glpk).