Partial Relaxation

Question

In the context of a larger optimization problem I realized that I am missing the skill to implement/exploit the following observation:

In the problem I was faced with two related sets of indicator variables which contributed to the objective function through two separate terms. I obtained very weak root relaxation bounds (only considered one part of the objective function) and correspondingly long solution times (Gurobi). While this slow approach eventually worked out I kept wondering how to do it better the next time:

When I manually relaxed the set of binary variables related to the part that was properly captured and retained the formulation the problem very quickly solved yielding a very strong LB - but of course just including the LB value does not help. So here comes the question: How to "suggest" such a partial relaxation scheme to the solver? Is there a modeling technique that achieves this or am I missing a feature/parameter? I first thought about lazy handling of integrality but could not figure out how to do this.

Answer 1

I think this is very close to the idea proposed by Yang et al. for the single source capacitated facility location problem (SS-CFLP). They relax the allocation/assignment variables to be continuous which leads to a CFLP as a relaxation of the SS-CFLP. This is what they call a partial relaxation as the location variables are still kept as binary.

They then embed this relaxation into the so called cut and solve framework (Climer and Zhang, 2006) which alternates between solving a relaxation with some additional "piercing cuts" called the dense problem generating a lower bound, and a sparse problem with many variables fixed from which upper bounds are generated.