When Does the Positive Semidefiniteness Constraint Help In Lifting Procedures

Levent Tuncel, Michel X. Goemans

We study the lift-and-project procedures of Lovász and Schrijver for 0-1 integer programming problems. We prove that the procedure using the positive semidefiniteness constraint is…