Automatic Strategy Selection in Google OR Tools
Date: 16 August 2021
Constraint solver in Google OR Tools provides the option to let the tool automatically select the best strategy to use according to the problem. In this article, I will explain how the strategy is picked and why you will want to choose the right strategy for your problem manually.
Constraint solver of Google OR Tools works in two steps:
- it creates a feasible solution that might not be very optimal using the first search strategy
- It improves the previously generated solution using the local search strategy (metaheuristic)
As of August 2021, there are 13 first search strategies and 5 local search strategies available.
The default First Search strategy and Local Search strategy is AUTOMATIC, which basically means that OR Tools will choose the best strategy itself according to the problem. So, how does OR Tools choose the right strategy for our problem?
First Solution strategy
The logic behind choosing the first search strategy is:
- If the problem has any pickup deliveries, then choose PARALLEL_CHEAPEST_INSERTION
- If the problem has any node precedences, then choose PARALLEL_CHEAPEST_INSERTION
- If the problem has at least one node where only one vehicle is allowed, then choose PATH_MOST_CONSTRAINED_ARC
- In all other cases, choose PATH_CHEAPEST_ARC
The default strategies work well enough in simple problems but should not be used for complex ones. For example, PATH_CHEAPEST_ARC worked best for the first phase of the routing tool I worked on, when there was only one dispatch hub, but was not able to give a solution when I added constraints in my algo.
Local Search strategy
If no Local Search strategy is explicitly selected, then the simplest local search algorithm available in OR Tools is chosen, i.e., GREEDY_DESCENT. GREEDY_DESCENT is the safest choice when choosing a local search strategy but it fails to provide optimal results even in very simple routing tasks. This is because it is unable to leave the local minima if the algo gets stucks which it will in most cases.
How to choose the best strategy?
The suggested way to choose the best strategy, both first solution and local search, is to try different variations on different input sizes and then analyze the time it takes to run and the objective function value to decide what works best for the problem.