OR Tools taking forever to solve VRP

[aire...@gmail.com]

Hi Team,

I am running a problem with 875 nodes and 1846 indices, and it is taking forever to run. It has around 200 vehicles. Is it realistic to solve such problem in OR-Tools? With smaller problem size, it is working fine and giving good results.

It is also not respecting this parameter:

search_parameters.time_limit.FromSeconds(300)

Which should give a timeout after 300 seconds, is it stuck somewhere?

Thanks

[amihai...@gmail.com]

How do you generate the transits? Perhaps it's stuck there

[Mizux Seiha]

1) IIRC time limit may be checked each time a solution is found to avoid to poll it too much, if in your case the solver is "stuck" in the search for an initial solution, you may notice this "forever" wait...

2) by default solver won't cache transit callback so if you are in Python you have to pay the conversion cost akak Python -> SWIG Python/C++ -> C++, which can be costly

to mitigate this you can:

* pass the transit Matrix directly instead of a callback so the matrix will be copied and stored in the C++ "space" so you won't have this penalty cost.
see: https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing.h#L402-L403 or
https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing.h#L487-L498

* Enable and increase the cache callback to at least 1846*1846 if you have enough memory, this can help by reducing the number to the transit callback

See:

ABSL_FLAG(bool, routing_cache_callbacks, false, "Cache callback calls.");

ABSL_FLAG(int64_t, routing_max_cache_size, 1000,

          "Maximum cache size when callback caching is on.");

ref: https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing_flags.cc#L121-L124

[Vincent Furnon]

On Thu, Jul 8, 2021 at 1:42 PM Mizux Seiha <mizu...@gmail.com> wrote:

1) IIRC time limit may be checked each time a solution is found to avoid to poll it too much, if in your case the solver is "stuck" in the search for an initial solution, you may notice this "forever" wait...

Actually the time limit should still be checked while building a first solution.

 

2) by default solver won't cache transit callback so if you are in Python you have to pay the conversion cost akak Python -> SWIG Python/C++ -> C++, which can be costly

to mitigate this you can:

* pass the transit Matrix directly instead of a callback so the matrix will be copied and stored in the C++ "space" so you won't have this penalty cost.
see: https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing.h#L402-L403 or
https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing.h#L487-L498

* Enable and increase the cache callback to at least 1846*1846 if you have enough memory, this can help by reducing the number to the transit callback

See:

ABSL_FLAG(bool, routing_cache_callbacks, false, "Cache callback calls.");

ABSL_FLAG(int64_t, routing_max_cache_size, 1000,

          "Maximum cache size when callback caching is on.");

ref: https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/constraint_solver/routing_flags.cc#L121-L124

Le jeudi 8 juillet 2021 à 12:33:41 UTC+2, amihai...@gmail.com a écrit :

How do you generate the transits? Perhaps it's stuck there

On Thursday, July 8, 2021 at 1:11:45 PM UTC+3 aire...@gmail.com wrote:

Hi Team,

I am running a problem with 875 nodes and 1846 indices, and it is taking forever to run. It has around 200 vehicles. Is it realistic to solve such problem in OR-Tools? With smaller problem size, it is working fine and giving good results.

It is also not respecting this parameter:

search_parameters.time_limit.FromSeconds(300)

Which should give a timeout after 300 seconds, is it stuck somewhere?

Thanks

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/d4af45fb-117d-4f26-9ad7-93fc975fa29bn%40googlegroups.com.

[aire...@gmail.com]

Thank you, using RegisterTransitMatrix helped a lot.

[aire...@gmail.com]

Also, can you explain why NodeToIndex() method gives only 1 output, as one node could be mapped to many indexes?

[GB]

Hello,

Is increasing the callback cache size via the flags equivalent to storing the transit matrix directly via RegisterTransitMatrix().? 

Thx

[blind.line]

In my experience, not the same but similar

Increasing cache size means solver takes time to hit the callback at least once for every node. 

Registering a matrix you just pass the data directly. 

I usually end up using the callback cache size approach because it is transparent. But eventually I want to switch my functions to generate matrices. 

But for all but trivial problems, you really should do one or the other. So much faster without the callbacks. 

James

On Jul 10, 2021, at 00:19, GB <guy.be...@gmail.com> wrote:

Hello,

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/d6048c48-5071-4292-9d22-53f0bbf4265fn%40googlegroups.com.

[GB]

Thx

I will check/compare when I get the time.