[SciPy-Dev] Combinatorial optimization in scipy.optimize

[Søren Fuglede Jørgensen]

On Wed, Jul 03, 2019 at 12:04:38PM -0700, Ralf Gommers wrote:
> Some of these are in scipy.sparse.csgraph already.

Thanks for the reference to scipy.sparse.csgraph; I had indeed missed that completely, and had I known about it, I might have actually expected something like linear_sum_assignment to live there, as touched upon in https://github.com/scipy/scipy/pull/10296.

> We indeed don't want to do everything that NetworkX already does, however
> if it's a well-known algorithm that would fit in with what we already have
> and focus on performance (which NetworkX does not do) then I think there's
> scope for more. For sparse.csgraph I think Jake implemented a set of
> standard algorithms that can be found in a graph algorithms introductory
> handbook.

I think it's definitely possible to find a handful of algorithms that match that description; the first that came to mind here would be the Edmonds--Karp and push--relabel algorithms for computing maximum flow.

> It also depends to some extent on who writes the code - technical code like
> that is often not the easiest to maintain, so it would make the
> conversation and review process a lot easier of there is a person (or two
> people) with a commitment to maintain the code going forward.

Makes sense. And I can see how that would also make you favor simpler versions of whatever algorithms might be relevant.

Søren