1
$\begingroup$

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!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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) $\endgroup$
    – Matus Telgarsky
    Commented Feb 9, 2010 at 6:25
  • 1
    $\begingroup$ I should add that the feasibility set can also be the empty set, or it can be unbounded (but still an intersection of halfplanes) $\endgroup$
    – Matus Telgarsky
    Commented Feb 9, 2010 at 6:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .