4 ms·
Interesting, I’ve always wondered if the assignment problem could be solved as continuous optimization. I’m familiar with manifold optimization but didn’t reali
by roger_ 2y ago
Interesting, I’ve always wondered if the assignment problem could be solved as continuous optimization. I’m familiar with manifold optimization but didn’t realize the permutation matrix could be expressed as a manifold.
Has this been applied to networks like DETR for object detection? I’ve never been clear on how they made the Hungarian algorithm differentiable (and it seems like their approach has issues).
- whatever1 2y agoOf course it can, but likely you will also need some search as well. In math programming, we create a relaxation of the assignment problem where all of the integer decisions are converted to continuous. Then you solve this super simple Linear Program. This is a theoretical lower bound on what the optimal assignment is. You can now start branch and bound search and find the optimal integer assignment. Now the trick is that we have identified over the decades cuts (inequalities) that you can apply to this initial relaxed problem, that they chop off irrelevant continuous space but let the integer solutions are untouched. If your cuts are good enough and the integer optimal solution is at the vertex of the chopped polytope, congratulations! You don't have to search anything!
- tmyklebu 2y agoNo cuts are necessary for minimum-weight bipartite matching as the constraint matrix is totally unimodular. Total unimodularity guarantees that any optimal basic solution is an integer solution. Moreover, well-known algorithms for linear programming like simplex and primal-dual methods have straightforward (and illuminating!) combinatorial interpretations when restricted to minimum-weight bipartite matching.
- whatever1 2y agoSpot on! I was just thinking about the case of having also complicating constraints. In the vanilla case is exactly as you say.
- oxavier 2y ago> Moreover, well-known algorithms for linear programming like simplex and primal-dual methods have straightforward (and illuminating!) combinatorial interpretations when restricted to minimum-weight bipartite matching. I you have any resource illustrating this point, please share. I would be very interested. I liked this video [0] about how the Hungarian Algorithm is a particular case of the primal-dual method and I am eager to dig further. [0] https://www.youtube.com/watch?v=T4TrFA39AJU https://www.youtube.com/watch?v=T4TrFA39AJU
- tmyklebu 2y agoThis was a popular topic in '80s linear programming books. Chvatal's "Linear programming," for instance, is carefully-written and devotes about 100 pages devoted to network simplex. Papadimitriou and Stieglitz's "Combinatorial optimization: algorithms and complexity" explicitly goes through primal-dual derivations of algorithms for shortest path, max flow, and min-cost flow (including bipartite matching). I haven't read it in any detail, but https://math.mit.edu/~goemans/PAPERS/book-ch4.pdf https://math.mit.edu/~goemans/PAPERS/book-ch4.pdf is online and might be to your liking.
- oxavier 2y agoMany thanks!
- marco_z 2y agoIt's incredible how many algorithms can be made differentiable end-to-end. E.g. in https://arxiv.org/abs/1905.11885 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.