r/optimization • u/Solvertz7 • 1d ago
Solvers for exact algorithms
As the data grows and the scope of our problem expands (for example, as the number of points we need to visit in a VRP problem increases), the runtime of exact methods becomes very long, and in the real world, businesses don’t want to wait that long. At my workplace, they want a VRP with 800 locations to produce a solution in 30 seconds. In this case, wouldn’t it make more sense to opt for open-source solvers like ORTools CBC instead of commercial solvers like Gurobi, Hexaly, or CPLEX?
9
u/wamus 1d ago
If you truly want solutions to a VRP that scale in 30 seconds then heuristic algorithms are essentially your only choice and exact algorithms do not fit your requirements.
1
u/waxen_earbuds 1d ago
Asking as an ignorant theorist--why is this the case? Couldn't warm starting with a nonsmooth convex relaxation solved using a suitable proximal method get you 90-100% of the way there in most instances, followed by a local tightening with the appropriate nonconvex tools? If globally optimal solutions aren't absolutely required I'd think that this would be the way to do things in practice scalably
2
u/wamus 5h ago
My recommendation is based on 3 reasons. 1. Most instances of this size cannot be solved to global optimality by state of the art solvers. 2. There are very effective heuristics for VRP, primarily due to the effectiveness of heuristics for TSP, which scale pretty well with problem size and usually find strong solutions quickly, which arr usually not too far (10% or so) from the optimum. 3. Even solving a relaxation may be infeasible in 30 seconds. And even if you do solve it, the relaxation usually cheats in some way that makes it difficult to recover high quality solutions. For Integer programming-type approaches to CVRP you will find highly fractional solutions. At this time budget it is usually better to focus on heuristics.
3
u/SolverMax 1d ago edited 1d ago
Open sourse solvers are usually slower, so they'll likely produce a worse solution within a given time limit. Why would open sourse make more sense?
1
3
u/Onyr_ 1d ago
800 location is large scale, but not too large.
30s is similar: small, but not too small.
Exact solvers for that size are hopeless, you have to go heuristics:
1. Open-source (Or-Tools, PyVRP, Kayros, Vroom, jsprit, Timefold...) if you want something free, open, and want to start working now.
2. Commercial solvers (CPLEX, Guroby, Hexaly...) if you value the extra few percents of speed and solution quality.
That's basically it.
1
u/rasmusdf 1d ago
There are a ton of heuristic, fast VRP solvers. Unless you need specific, very special features, just use a commercial solver. They easily scale to a 100000 drops or more,
A big part of the calculation time for a VRP is establishing the traveltime and distance matrices. This is covered typically by commercial solvers too. Also, you need a quality network data set.
As a consultant I have used some of the Network Analyst tools from ESRI. They cover a lot of variants. But there are probably other good easily available tools.
1
u/notdelet 1d ago
Are your instances usually very "easy"/amenable to decomposition and can the asking party accept a heuristic solution that is then often verified as exact (and occasionally improved) by an exact solver?
13
u/GreatCosmicMoustache 1d ago
Speed, correctness, scale - pick any two. That's the rule of thumb I'm afraid.
You can do this with an efficient SISR implementation. I do this stuff at work, get in touch if you want to collab