Through tears and mud, how else?

E.g the pieces from the rows you eliminate reappear at random at the top row.

probably one needs something like lazy evaluation, so that things are only computed if needed.

True, but I'm thinking more from a UI standpoint -- how would you present that complexity to the user, and how would you help them pare it down?

Boumal was advised by Absil IIRC :) And in fact you can see this in his more modern presentation of the material.

Good pointer! I did know about CVXPY but haven't used it yet. Though in requiring everything to be (log-)convex it constrains the user programs quite a bit, but I imagine it would have worked in this case because the objective is linear and the feasible set convex. I won't deny the role accident and force of habit had in picking this particular implementation path; I used Pytorch because it's my daily driver :D and because I had found 'mctorch' which provided the Riemann SGD logic.

Actually, you can solve the assignment problem as a linear program (LP). Just do

    min sum_i sum_j c_{ij}*x_{ij}

    s.t. sum_i x_{ij} == 1, for all j
         sum_j x_{ij} == 1, for all i

and you automagically get an integer solution in the x_{ij} due to the structure of the constraints.

CVXPY would be a good way to implement this these days.

It's incredible how many algorithms can be made differentiable end-to-end.

E.g. in https://arxiv.org/abs/1905.11885 "Differentiable ranks and sorting using optimal transport" they show how a relaxation of an array sorting procedure leads to differentiable rank statistics (quantiles etc.). The underlying theory is quite close to what I show in the blog post.

In DETR they don't actually use a differentiable Hungarian algorithm, it's only used to score their neural predictions outside of the training loop IIUC.

Yes, the problem can now be solved efficiently with a scikit one-liner, but the aim of this post was more speculative rather than beating the benchmark :)

Oh yeah that's sure, i wasn't trying to diminish the content, the opposite. as in, it was so complex and out of what i expected that i was lucky to have a library that could solve it for me

Author here! Thank you f1shy for sharing.

Sugoi! I imagine this approach would be very useful in learning any other language, too.

An interesting connection between combinatorial optimization and differential geometry. And some Pytorch too, because when all you have is a hammer..

I built most of this one year ago, but only now managed to write it up. I enjoyed the change of pace of a pure speculative experiment (with some deep connections to a bunch of interesting theory and applications), and I hope you will enjoy reading about it too.