[tmyklebu]

No 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.

[oxavier]

> 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

[tmyklebu]

This 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 is online and might be to your liking.

[oxavier]

Many thanks!

[whatever1]

Spot on! I was just thinking about the case of having also complicating constraints. In the vanilla case is exactly as you say.