semidefinite lifting

Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra

  • Sung-Pil Hong
  • Levent Tunçel
    • Categories 0-1 Programming, Semi-definite Programming Tags , , ,

    We present a unifying framework to establish a lower-bound on the number of semidefinite programming based, lift-and-project iterations (rank) for computing the convex hull of the feasible solutions of various combinatorial optimization problems. This framework is based on the maps which are commutative with the lift-and-project operators. Some special commutative maps were originally observed by … Read more

    Lift-and-project ranks and antiblocker duality

  • Laszlo Liptak
  • Levent Tunçel
    • Categories Combinatorial Optimization Tags , , , , ,

    Recently, Aguilera et al.\ exposed a beautiful relationship between antiblocker duality and the lift-and-project operator proposed by Balas et al. We present a very short proof of their result that the \BCC-rank of the clique polytope is invariant under complementation. The proof of Aguilera et al. relies on their main technical result, which describes a … Read more

    The stable set problem and the lift-and-project ranks of graphs

  • Laszlo Liptak
  • Levent Tunçel
    • Categories Combinatorial Optimization, Graphs and Matroids, Integer Programming Tags , , , ,

    We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lov\’asz and Schrijver, in the context of the stable set problem on graphs. We investigate how the procedures’ performances change as we apply fundamental graph operations. We show that the odd subdivision of an edge and the subdivision of a star operations … Read more