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
Some of the linear programs which comes to my mind are
- George Dantzig’s linear program for Traveling Salesman Problem. You can find a nice description of the result here.
- Flow based Linear program for Capacitated Facility Location Problem. This was a FOCS2014 paper which settled the long standing open problem of whether there is a linear program for this problem with constant integrality gap. You can find the paper here.
I'm sure there are a lot more of them out there.