0/1 optimization and 0/1 primal separation are equivalent
Friedrich Eisenbrand, Giovanni Rinaldi, Paolo Ventura · 2002
The 0/1 primal separation problem is: Given an extreme point x of a 0/1 polytope P and some point x , nd an inequality which is tight at x, violated by x and valid for P or assert that no such inequality exists. It is known that this separation variant can be reduced to the standard separation problem for P . We show that 0/1 optimization and 0/1 primal separation are polynomial time equivalent. This implies that the problems 0/1 optimization, 0/1 standard separation, 0/1 augmentation, and 0/1 primal separation are polynomial time equivalent. We apply this result to the perfect matching problem. Here, primal separation is easier than its standard version. We present an algorithm for primal separation, which rests only on simple max-flow computations. Consequently, we obtain a very simple proof that a maximum weight perfect matching of a graph can be computed in polynomial time. In contrast, the known standard separation method involves Padberg and Rao's minimum odd cut algorithm, which itself is based on the construction of a Gomory-Hu tree.