Minimum bipartite matching via Riemann optimization

Re:Minimum bipartite matching via Riemann optimization by marco_z on Wednesday January 08, 2025 @03:32PM (#42638157)

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.

[ Parent | on HN ]

Re:Minimum bipartite matching via Riemann optimization by cschmidt on Wednesday January 08, 2025 @03:49PM (#42638300)

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.

[ Parent | on HN ]