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!
Best Answer
MILP is an inherently difficult (NP-hard) problem, so the behavior of your solver will vary greatly based on which heuristics it uses, what branching strategy you use, and the formulation of the original problem.
It is possible that your MILP solver has a different default behavior for problems with an objective function and pure feasibility problems. Some heuristics (such as the feasibility pump) work well for a wide variety of feasibility problems, but may not necessarily be the most efficient for other classes of problems.
In short, efficiently solving MILPs is a black art that forms much of the basis of operations research.