When solving a MILP (mixed integer linear program) using a linear relaxation, the solver finds a feasible solution much faster if there is no objective function. The same problem with an objective takes much much longer and doesn't find any feasible solution for a long time.

Is there an explanation for that?

I'm now using a two phase approach. I first solve the problem without an objective, then I solve it again with an objective and the starting point is the feasible one from phase 1. Is this approach ok? The best solution shouldn't be discarded!