[SciPy-Dev] Combinatorial optimization in scipy.optimize
Ralf Gommers
ralf.gommers at gmail.com
Wed Jul 3 15:04:38 EDT 2019
On Thu, Jun 27, 2019 at 4:08 AM Søren Fuglede Jørgensen <
scipy-dev at fuglede.dk> wrote:
> Hi SciPy-Dev
>
> This question is motivated by the recent improvements to
> scipy.optimize.linear_sum_assignment. [0] Here, we get a much improved
> algorithm for solving minimum weight perfect matching in bipartite graphs
> (which is excellent).
>
> Now, this problem is one in a large family of combinatorial optimization
> problems on packing and covering, and what I'm wondering is if SciPy should
> be the home for a general class of efficient algorithms for solving those?
>
> Most of these can be phrased in terms of graph theory, and indeed networkx
> already contains implementations of many classical algorithms (and I was
> surprised to find that it didn't have anything matching
> linear_sum_assignment directly; it does have an implementation of the
> Blossom algorithm). So there's some overlap of scope here, but I guess
> that's not a problem in and by itself, but it had me wondering where the
> split should be?
>
> Just to phrase this in terms of (a very incomplete list of) examples (some
> of which have polynomial solutions, some of which don't), would there be
> appetite for including into scipy.optimize algorithms for solving e.g.
>
> 1. other covering/packing problems (e.g. min set/vertex/edge cover,
> maximum matching, ...),
> 2. maximum flow,
> 3. shortest path,
> 4. travelling salesman,
>
5. circuit minimization?
>
Some of these are in scipy.sparse.csgraph already.
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.
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.
Cheers,
Ralf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20190703/bbff82fb/attachment.html>
More information about the SciPy-Dev
mailing list