From class, I learnt that problems like traveller salesman have a Linear programming representation with exponentially many constraints. Using method of separation, this problem is solved rather successfully in practice.
In that LP, the number of variables in constraints in roughly equal to the number of objective variable.
In my material science research, I have another problem which also has a LP formulation with exponentially many constraints. However, the number of variables in constraints (mostly variables with 0 objective value) are also exponential.
For example, when n=3, we we have:
min: c[1]x[1]+c[11]x[11]+c[1~1]x[1~1]
s.t. x[1]+x[0]=1;
x[1]=x[10]+x[11];
x[1]=x[01]+x[11];
x[0]=x[01]+x[00];
x[0]=x[00]+x[10];
x[00]=x[001]+x[000];
x[00]=x[100]+x[000]
x[01]=x[010]+x[011];
x[01]=x[001]+x[101];
x[10]=x[100]+x[101];
x[10]=x[010]+x[110]
x[11]=x[110]+x[111];
x[11]=x[011]+x[111];
x[1~1]=x[101]+x[111];
x>=0;
Notice that there are roughly 2^n constraints. What is the best method to approach this problem for higher n? If you are interested in writing papers together on this class of problem, Please do not hesitate to contact me, thank you:)