2
$\begingroup$

I want to solve a Mixed Integer problem with several constraints. Gurobi or Google OR tools solve such problems. Though I am not sure, I think they use an exact method such as branch and bound or plane cut. Whereas, OptaPlanner is a metaheuristic solver. Does it give equally good results in terms of optimality?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ It depends. If the MIP solver can close the gap quickly, a (meta-)heuristic may not be that interesting. If the MIP solver is struggling, looking into a (meta-)heuristic is more appealing. Meta-heuristics don't provide bounds, so it is always difficult to say much about the quality of the solution. (And worse: they don't know really when to stop; they don't know if they solved the problem.) Not that high-end MIP solvers contain a battery of heuristics, so even for problems where a MIP solver can not prove optimality, it may be able to find good solutions quickly. $\endgroup$
    – Erwin Kalvelagen
    Commented May 31, 2023 at 13:24

2 Answers 2

Reset to default
1
$\begingroup$

It depends on the use case. The right tool for the job.

Generally speaking, in my experience, for Vehicle Routing Problems and many other use cases, when scaling out, a good metaheuristics solver (such as OptaPlanner/Timefold, but there are others) will always outperform a good MIP solver. Typically MIP solvers go out of memory around 2000 VRP locations in single dataset. Your mileage may vary.

If I recall correctly, Google OR Tools wrote a CVRP-specific (non-MIP) solver - with separate API, mostly unrelated to their MIP solver - to deal with this reality.

These OptaPlanner/Timefold use cases work well with a metaheuristic solver. That's non-complete list, but similarly there is a long list of ideal for MIP solver use cases.

Improve this answer
$\endgroup$
3
$\begingroup$

First, @Geoffrey De Smet, is the creator of Optaplanner and might answer your question with more details about his tool. But, as you want to compare the exact solution, please be aware, Gurobi and OR-tools MIP solver use, in general, the branch and cut algorithm to solve a MIP problem based on the linear relaxation of the original model that can be solved optimality by Simplex or other efficient exact algorithms. However, the best way to compare is to test a provided solution by Optaplanner as a warm-start on its equivalent MIP model to examine the quality of the solution you have.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes, of course, I can compare the results but that is time-consuming. Wanted to make sure quickly :) $\endgroup$
    – LSG
    Commented May 30, 2023 at 14:20
  • 2
    $\begingroup$ @LSG, as a quick answer, it cannot provide an optimal solution at least with an provable sense. $\endgroup$
    – A.Omidi
    Commented May 30, 2023 at 14:36

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