Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators

We consider operators acting on convex subsets of the unit hypercube. These operators are used in constructing convex relaxations of combinatorial optimization problems presented as a 0,1 integer programming problem or a 0,1 polynomial optimization problem. Our focus is mostly on operators that, when expressed as a lift-and-project operator, involve the use of semidefiniteness constraints … Read more

Lov\'{a}sz-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs

We study the Lov\'{a}sz-Schrijver lift-and-project operator ($\LS_+$) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the $\LS_+$-operator generates the stable set polytope in one step has been open since 1990. We call these graphs … Read more

A Comprehensive Analysis of Polyhedral Lift-and-Project Methods

We consider lift-and-project methods for combinatorial optimization problems and focus mostly on those lift-and-project methods which generate polyhedral relaxations of the convex hull of integer solutions. We introduce many new variants of Sherali–Adams and Bienstock–Zuckerberg operators. These new operators fill the spectrum of polyhedral lift-and-project operators in a way which makes all of them more … Read more