VRP increase cache

[Fadi Younes]

Hi everyone,

I'm running VRP problem on very big input, and running takes hours and hours. 

I've read that increasing the cache callback could help in a better performance. Can anyone tell me how to do that in Python? I couldn't find anything related to this in Python.

Thank you!

[blind.lin...@gmail.com]

This is more cargo cult programming than anything, as this is not super well documented, but...

Reading through routing.cc and searching for max_callback_cache_size, it is clear that the cache size is really just used to set a boolean:

cache_callbacks_ = (nodes_ <= parameters.max_callback_cache_size());

So the max callback cache size has to be bigger than the number of nodes.

Later, the actual cache size used is (nodes + number of vehicles)^2:

  if (cache_callbacks_) {
    const int size = Size() + vehicles();
    std::vector<int64_t> cache(size * size, 0);

So just in case the developers "fix" this inconsistency and the boolean check changes in a future version, and because I really want caching to always happen, I generally do (in python)

    model_parameters = pywrapcp.DefaultRoutingModelParameters()
    model_parameters.max_callback_cache_size = 2 * num_nodes * num_nodes

This should turn on caching of all of your callback functions in the dimension definitions. I have never noticed an issue with RAM doing this, and I am not sure why it is not the default always, as the improvement in running time is massive.

Regards,

James

-- 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/2a03b31b-6fb0-4e75-b329-a8ccf324f658n%40googlegroups.com.

--
James E. Marca
Activimetrics LLC

[Fadi Younes]

Thank you so much James!

[Prateek Khandelwal]

On Sunday, July 17, 2022 at 2:56:48 PM UTC+5:30 fadi.yo...@gmail.com wrote:

Thank you so much James!

Did it work? Did you see any improvements in the route generated? 

 

On Thursday, July 14, 2022 at 5:47:17 PM UTC+3 blind.lin...@gmail.com wrote:

This is more cargo cult programming than anything, as this is not super well documented, but...

Reading through routing.cc and searching for max_callback_cache_size, it is clear that the cache size is really just used to set a boolean:

cache_callbacks_ = (nodes_ <= parameters.max_callback_cache_size());

So the max callback cache size has to be bigger than the number of nodes.

Later, the actual cache size used is (nodes + number of vehicles)^2:

  if (cache_callbacks_) {
    const int size = Size() + vehicles();
    std::vector<int64_t> cache(size * size, 0);

So just in case the developers "fix" this inconsistency and the boolean check changes in a future version, and because I really want caching to always happen, I generally do (in python)

    model_parameters = pywrapcp.DefaultRoutingModelParameters()
    model_parameters.max_callback_cache_size = 2 * num_nodes * num_nodes

This should turn on caching of all of your callback functions in the dimension definitions. I have never noticed an issue with RAM doing this, and I am not sure why it is not the default always, as the improvement in running time is massive.

Regards,

James

Passing time_matrix is not available in python? Or enabling caching using ABSL FLAGS not available in python (https://groups.google.com/g/or-tools-discuss/c/ViEPGrYBils)? Or Am I missing something? 

Will definitely try the solution suggested. Need to do something like this, right? 

```

model_parameters = pywrapcp.DefaultRoutingModelParameters()

model_parameters.max_callback_cache_size = 2 * num_nodes * num_nodes

search_parameters = pywrapcp.DefaultRoutingSearchParameters()

if (

route_group_config["first_solution_strategy"]

== constants.PARALLEL_CHEAPEST_INSERTION

):

search_parameters.first_solution_strategy = (

routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION

)

else: # default PATH_CHEAPEST_ARC

search_parameters.first_solution_strategy = (

routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC

)

search_parameters.local_search_metaheuristic = (

routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH

)

search_parameters.time_limit.FromSeconds(int(solution_time))

# search_parameters.log_search = True

# Solve the problem.

solution = routing.SolveWithParameters(search_parameters)

```

[Fernanda Bia Peteam]

I tried to work with max_callback_cache_size but I got "AttributeError: Protocol message RoutingSearchParameters has no "max_callback_cache_size" field"

I'm working with python 3.8

[blind.line]

Are you modifying the correct parameters? You should read more carefully. My guess is you’re modifying the SearchParameters, when you should be setting the value on RoutingParameters. 

James

On Nov 30, 2022, at 11:53, Fernanda Bia Peteam <fernand...@gmail.com> wrote:

I tried to work with max_callback_cache_size but I got "AttributeError: Protocol message RoutingSearchParameters has no "max_callback_cache_size" field"

--

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/69f793c7-fd73-49d2-9fdd-05b0b67b9a5en%40googlegroups.com.

[Fernanda Bia Peteam]

You're right, thats what happened xD Sorry!
Thank you very much!

[Mizux Seiha]

Adding link here for easy retrieval in the future....

v9.8 src code link:
Cache (need to have parameter `max_callback_cache_size`  higher than the number of node returned by the `IndexManager`):
https://github.com/google/or-tools/blob/d09c2ba8493e66436f5643276abc10036fc2f8fd/ortools/constraint_solver/routing.cc#L387-L390
https://github.com/google/or-tools/blob/d09c2ba8493e66436f5643276abc10036fc2f8fd/ortools/constraint_solver/routing.cc#L420-L422

Cache size computation
https://github.com/google/or-tools/blob/d09c2ba8493e66436f5643276abc10036fc2f8fd/ortools/constraint_solver/routing.cc#L540-L543