Using Lemon Graph Library (http://lemon.cs.elte.hu/trac/lemon) for minimum cost flow subroutine. Minimum cost flow algorithm from Google OR tools also works but slower.
Todo:
- Control the error bound with numerical error analysis
- Leverage the old states of network simplex for faster min-cost flow subroutine.
References:
- Karger, David, and Serge Plotkin. "Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows." STOC. Vol. 95. 1995.
- Leighton, Tom, et al. "Fast approximation algorithms for multicommodity flow problems." Journal of Computer and System Sciences 50.2 (1995): 228-243.
- Goldberg, Andrew V., et al. "An implementation of a combinatorial approximation algorithm for minimum-cost multicommodity flow." International conference on integer programming and combinatorial optimization. Springer, Berlin, Heidelberg, 1998.