What are some of the most ingenious linear programs developed for tackling hard combinatorial 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