Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
1  
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.