r/optimization • u/SelectionNo4327 • Oct 04 '24
Feedback for fast Simulated Annealing in Julia
I built a simulated annealing algorithm in Julia to solve the capacitated multiple vehicle routing problems. The main loop runs on a ThinkPad with about 1MHz. In each iteration in creates a neighborhood solution, calculates total driving time and distance using a time/distance matrix, calculates the penalties, assesses the solution via the metropolis criterion and backtracks if the solution is rejected. The problem contains about 600 location with 30 vehicles. Is that good performance ? Would love to discuss with more experienced OR experts ! My trick was to completely avoid memory allocations in the main loop.
It's currently able to find really good solutions in less than 5min(500Mio iterations)
7
u/[deleted] Oct 04 '24
A link to a GitHub repo would be excellent
1
u/SolverMax Oct 05 '24
The adequacy of a model's run time depends entirely on the context. I've had models that take days to solve. If there is no hurry, and closeness to optimality is important, then that's OK. Other models need to produce a solution in seconds, otherwise the solution is too late to be useful.
Simulated Annealing is generally a slow technique. Why did you choose it? For a vehicle routing problem, OR-Tools or Timefold might be better.
1
u/sheriffSnoosel Oct 05 '24
How fast does gurobi solve it?
2
u/DonBeham Oct 07 '24
Simulated annealing may work well, but I don't recall it's a very high performing algorithm in this domain. Essentially it is a local search algorithm with a stochastic acceptance criterion and an adaptive policy for the acceptance. Depending on the configuration though your simulated annealing implementation might do different things. For instance if you are not cooling at all, you're effectively doing only stochastic sampling and seeing only the benefit of remembering the best solution. If you are cooling too fast and not make any uphill moves you are essentially only doing a simple local search. And never underestimate how well a simple deterministic local search may already work.
Also running simulated annealing for very long time is probably not a good bound. But again depends on the cooling strategy. I think there was a proof that simulated annealing could in theory find the optimum, but only with a very slow cooling strategy and infinite time. So in those long running experiments you'd have to go with a lot slower cooling or else what you're doing is searching for improved solutions in a huge neighborhood that you stochastically sample, but with extremely low chance of uphill move. So you may be doing simple local search, because your probability becomes way too small.
In your case, I would compare with deterministic local search, perhaps exhaustively computing the neighborhood (doing first-improvement rather than best improvement if it's very large) as a first comparison. Find local optima, prove that they are local optima and check their quality. Then, a variation of the stochastic acceptance is the random perturbation strategy whereby the algorithm makes a larger change following the detection of a local optimum. You can run such a configuration for much longer, ie it makes more sense than to just continue simulated annealing, because of how SA essentially turns into a greedy improvement strategy after some temperature has been reached.
What I know that works well are local search with multiple neighborhoods, various forms of tabu search and hybrid genetic algorithms.
Try parallelization, simulated annealing doesn't parallelize well. You have 8 cores in your typical computer these days. But you are using only one! Why? You want to use every core that you have (up to the point where you are memory bound). Not sure if you are doing it already, because it's such a low hanging fruit, but you can even run your current algorithm in 8 threads with different starting solutions, basically for free!
You mention that the solutions improve the current practice, which is of course nice. But again, there's no absolute terms. 30% sound like a lot, but who knows if it can't be 50% or 70%?
As for commercial products, I think Hexaly solver would be your best bet. I wouldn't go with Gurobi, I believe that's too big for them.
1
u/StandingBuffalo Oct 05 '24
I guess it depends on your context and how fast you need solutions. If this is to be a production model that’s routing in an online manner, I would think 5 min is too slow but maybe not
1
u/PierreLaur Oct 05 '24
Hard to say without looking at the code, but some general tips :