| Article ID: | iaor20041207 |
| Country: | United States |
| Volume: | 26 |
| Issue: | 4 |
| Start Page Number: | 796 |
| End Page Number: | 815 |
| Publication Date: | Nov 2001 |
| Journal: | Mathematics of Operations Research |
| Authors: | Tuncel L., Goemans M.X. |
We study the lift-and-project procedures of Lovasz and Schrijver for 0–1 integer programming problems. We prove that the procedure using the positive semidefiniteness constraint is not better than the one without it, in the worst case. Various examples are considered. We also provide geometric conditions characterizing when the positive semidefiniteness constraint does not help.