In this work, we study the strength of the Chvatal-Gomory cut generating procedure for several hard optimization problems and compare it to lift and project hierarchies. We show that for some problems eg hypergraph matching, Chvatal-Gomory cuts perform well and give linear programs which have much smaller integrality gaps than those obtained by lift and project hierarchies. On the other hand, we show that for other problems such as k-CSP, unique label cover, maximum cut, and vertex cover they perform worse than lift and project hierarchies.
This is joint work with Kunal Talwar.
Copyright. All Rights Reserved.