lift-and-project methods

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

  • Yu Hin (Gary) Au
  • Levent Tunçel
    • Categories 0-1 Programming, Convex Optimization, Semi-definite Programming Tags , , , , , ,

    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

  • S. Bianchi
  • Mariana Escalante
  • Levent Tunçel
  • G. Nasini
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

    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

  • Yu Hin (Gary) Au
  • Levent Tunçel
    • Categories Combinatorial Optimization, Integer Programming, Linear, Cone and Semidefinite Programming Tags , , , , ,

    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