Reformulation is a good strategy for many hard problems.

It might also be possible to add problem-specific cuts/heurstics to the solver so that it can solve it fast.