What are some of the most ingenious linear programs developed for tackling hard combinatorial problems? What are some known ingenious linear programs that have been developed for tackling hard combinatorial optimization problems, especially any linear programs which had helped in getting good approximation algorithms for long standing open questions related to NP-hard optimization problems.
The relaxation of Calinescu, Karloff and Rabani for the undirected Multiway Cut problem is one my favorites. Had a big influence on subsequent work.
http://www.sciencedirect.com/science/article/pii/S0022000099916872