Solver throws error when run with ~15K locations/nodes

[ammark100]

What version of OR-Tools and what language are you using?
Version: 9.7
Language: Python

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)
Routing Solver

What operating system (Linux, Windows, ...) and version?
Windows and Linux both

What did you do?
Steps to reproduce the behavior:
I have a situation where I need to solve a problem with more than 15K node visits and approximately 1K vehicles. Even if I set the time to ~10 mins, the solver takes more than 10 mins (probably 11-12 mins) but then throws an error. It works perfectly fine if I just trim the same data to about 5K nodes but as soon as I increase the nodes, it doesn't solve. Can someone please help me?
Thanks in advance

[lperron]

Most likely an error in your code. Try adding try catch around your callbacks.

Anyways with a report so vague, we cannot do anything.

[ammark100]

Sorry for not including details, I have some standard dimensions as mentioned in the docs (capacity and keeping track of time), then adding penalties

penalty = 1000000
for node in range(1, len(distance_matrix)):
     routing.AddDisjunction([manager.NodeToIndex(node)], penalty)

and then I am using the following search parameters

search_parameters = pywrapcp.DefaultRoutingSearchParameters()

search_parameters.first_solution_strategy  = (
   routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)  

search_parameters.local_search_metaheuristic = (
   routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)

search_parameters.time_limit.FromSeconds(self.plan_time_limit_in_sec) 

[Mizux]

Did you monitor the memory footprint when running the code ?

[ammark100]

Thanks for your reply. Do you mean checking the memory of a system (i.e. vmstat or task manager in case of windows) or is there any function in the library that keeps a track of memory footprint?
I checked memory usage from my PC (checking Task manager of my windows machine) and it was occupying almost 99% of the memory, so probably having memory issues.

[ammark100]

Some further debugging led me to my function where I am calculating my distance matrix. That has O(n^2) complexity and that becomes a blocker. Below is the function. Any recommendations on how to find distance matrices?

def compute_euclidean_distance_matrix(self, locations):
        distances = {}
        for from_counter, from_node in enumerate(locations):
            distances[from_counter] = {}
            for to_counter, to_node in enumerate(locations):
                if from_counter == to_counter:
                    distances[from_counter][to_counter] = 0
                else:
                    # Euclidean distance
                    distances[from_counter][to_counter] = (int(
                        self.euclidean_distance(from_node, to_node) * 100)) #multiply by the factor of 100 for better result
        return distances
        

cc: @Mizux @lperron

[Mizux]

you can increase the "cache" of routing so the solver should only call N^2 time your function.
Or you can precompute the matrix then use the overload method (registerMatrixTransit iirc) to pass the matrix to routing.

Anyway this is a limitation of the implementation of the routing solver to call all pair as warmup...

TransitMatrix:

or-tools/ortools/constraint_solver/routing.h

Lines 589 to 590 in d09c2ba

	int RegisterTransitMatrix(
	std::vector<std::vector<int64_t> /*needed_for_swig*/> values);

Cache (need to have parameter max_callback_cache_size higher than the number of node returned by the IndexManager):

or-tools/ortools/constraint_solver/routing.cc

Lines 387 to 390 in d09c2ba

	RoutingModel::RoutingModel(const RoutingIndexManager& index_manager,
	const RoutingModelParameters& parameters)
	: solver_(CreateSolverFromParameters(parameters)),
	nodes_(index_manager.num_nodes()),

or-tools/ortools/constraint_solver/routing.cc

Lines 420 to 422 in d09c2ba

	// Active caching after initializing vehicle_to_transit_cost_ to avoid
	// uselessly caching ReturnZero.
	cache_callbacks_ = (nodes_ <= parameters.max_callback_cache_size());