# Why is solving a MILP w/o an objective function so much faster?

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!

-

## 2 Answers

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.

-

For any LP solver, the first step is always to find some feasible solution (any point within the simplex). It then tries to walk along (or within) the simplex until it reaches the optimal point. This second step can take a long time, and isn't necessary if you don't care which feasible point it returns.

-
A couple things wrong here. first, the feasible set is a convex polytope, not necessarily a simplex. the simplex algorithm indeed walks the vertices, however there are many algorithms which behave otherwise (for instance en.wikipedia.org/wiki/Interior_point_method) – Matus Telgarsky Feb 9 '10 at 6:25
I should add that the feasibility set can also be the empty set, or it can be unbounded (but still an intersection of halfplanes) – Matus Telgarsky Feb 9 '10 at 6:26