How simplex guaratee integral solutions for Bipartite matching problem
AnsweredI found the following statement in the User guide here: "The important point to note is that solving this continuous model with the simplex algorithm guarantees an integral solution which can therefore be used to select a set of edges for the matching." And I'm interested in how it's guaranteed. Is it a commonly known fact or does it depend on the implementation of the simplex method?
-
Official comment
This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
Hi Dmytro,
This is both a statement about the matching problem and the simplex algorithm.
The simplex algorithm always produces a solution to a LP corresponding to a vertex of the polyhedron defined by the linear constraints. If the coordinates of this vertex are integral, then we have an integral solution. If every vertex is integral, we have what is called an "integral polyhedron", and if the simplex algorithm finds a feasible solution then it is guaranteed to be integral.
The standard formulation for the matching problem is known to correspond to an integral polyhedron, which is why we can solve it using the simplex algorithm, without needing to appeal to MIP algorithms.
For more information see the following:
https://en.wikipedia.org/wiki/Matching_polytope
and for why we know the polyhedron is integral:
https://en.wikipedia.org/wiki/Unimodular_matrix
(it is particularly useful to familiarize yourself with the "Common totally unimodular matrices" mentioned).- Riley
0 -
Thanks for your detailed answer! Now all is clear to me.
0
Post is closed for comments.
Comments
3 comments