How simplex guaratee integral solutions for Bipartite matching problem

Answered

Dmytro Cherniakin

October 04, 2023 19:44

• 
• 
• 

I 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?

Related to

• Simplex

0

• 

  Riley Clement

  • Gurobi Staff

  October 04, 2023 23:42

  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
• 

  Dmytro Cherniakin

  October 05, 2023 09:18

  • 
  • 
  • 

  Thanks for your detailed answer! Now all is clear to me.

  0

Please sign in to leave a comment.