Suppose you have a combinatorial optimization problem that is formulated as a mixed integer linear program (minimization). The problem size is denoted $n$ and the expected $n$ is around $100$. The integer program has $O(n^5)$ variables and $O(n^2)$ constraints and its LP relaxation bound is very good. We also have a very good feasible solution that is at most $1$-$5\%$ far from optimal.
The issue is that there are so many variables and it takes so much run-time even for the LP-relaxation. I was wondering how we could fix some of the decision variables given the feasible solution. We do not have the lower bound at the beginning so it cannot be used. I know that MIP solvers have their own preprocessing, but this can happen only after the LP is loaded to the memory which is an issue by itself.
What do you suggest? Are you aware of any reference or paper in which the knowledge of having a good upper bound is used to fix the decision variables of an optimization problem?
I think my question is essentially reduced to the following:
For a combinatorial optimization problem, how can we obtain a non-trivial lower bound on the optimal objective value given a good feasible solution!?