minimum bipartite matching via Riemann optimization

A sample run, with cost lower bound (LB) given by the combinatorial (Munkres) solution and corresponding solution in dashed red line. In d=10, the Birkhoff polytope has 3628800 corners so it's likely SGD got stuck in a local minimum.

---

Instead of a scipy one-liner ( linear sum assignment ), we take the panoramic route and formulate it as an optimization problem over the manifold of doubly-stochastic matrices, hoping to end up in a corner of the Birkhoff polytope.

If it works I'll write a blog post about it UPDATE: it works

UPDATE: blog post: https://ocramz.github.io/posts/2023-12-21-assignment-riemann-opt.html

References

• https://en.wikipedia.org/wiki/Assignment_problem
• https://en.wikipedia.org/wiki/Doubly_stochastic_matrix