0/1 Optimization and 0/1 Primal Separation are Equivalent

powerful tool to prove that certain combinatorial optimization
problems can be solved in polynomial time.

Primal separation is less general and simpler than
(standard) separation. However, for the important case of
0/1 programming we establish an according equivalence result.

As an application, we obtain a very simple proof that maximum
matchings of graphs can be computed in polynomial time. Our
primal separation rests only on simple (s,t)-flow computations
in contrast to the standard separation algorithm which requires
the computation of minimum weight odd cuts.
---