Abstract.
The 0/1 primal separation problem is: Given an extreme point x¯ of a 0/1 polytope P and some point x *, find 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.
Then we provide polynomial time primal separation procedures for matching, stable set, maximum cut, and maximum bipartite graph problems, giving evidence that these algorithms are conceptually simpler and easier to implement than their corresponding counterparts for standard separation. In particular, for perfect matching we present an algorithm for primal separation that rests only on simple max-flow computations. In contrast, the known standard separation method relies on an explicit minimum odd cut algorithm. Consequently, we obtain a very simple proof that a maximum weight perfect matching of a graph can be computed in polynomial time.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received: August 20, 2001 / Accepted: April 2002 Published online: December 9, 2002
RID="⋆"
ID="⋆" This research was developed while the author was on leave at the Istituto di Analisi dei Sistemi ed Informatica, Viale Manzoni 30, 00185 Roma, supported by the project TMR-DONET nr. ERB FMRX-CT98-0202 of the European Union.
Mathematics Subject Classification (2000): 90C10, 90C60, 90C57
Rights and permissions
About this article
Cite this article
Eisenbrand, F., Rinaldi, G. & Ventura, P. Primal separation for 0/1 polytopes. Math. Program., Ser. A 95, 475–491 (2003). https://doi.org/10.1007/s10107-002-0309-y
Issue Date:
DOI: https://doi.org/10.1007/s10107-002-0309-y