routing solver is stuck and ignores time out

[Rummel]

Hello,

I already posted my problem on stackoverflow.

I'm using or-tools 9.7 on windows 10 and the routing solver with python.

I need to solve many VRPPDs and most of them working without any problem. But sometimes in some scenarios one problem is stuck (it does not solve within ms, as the others do) and I need to cancel the calculation.

Also the timeout defined with search_parameters.time_limit.seconds = 1 seems not to work. I just tried solver.TimeLimit(time_limit_in_ms) too, but it didn't help either.

It is difficult to create a minimal example, because the problem rarely occurs. I removed some constraints, but the data model is relatively large.

Can you try to run my example and tell me, if it creates a solution on your machine?

My output is:

```

## Done

<bound method Solver.Parameters of <ortools.constraint_solver.pywrapcp.Solver; proxy of <Swig Object of type 'operations_research::Solver *' at 0x000001B970C98F60> >>
WARNING: All log messages before absl::InitializeLog() is called are written to STDERR
I0000 00:00:1698048441.894696    8204 search.cc:276] Start search (memory used = 35.41 MB)
I0000 00:00:1698048441.894991    8204 search.cc:276] Root node processed (time = 0 ms, constraints = 279, memory used = 35.65 MB)
I0000 00:00:1698048441.895208    8204 search.cc:276] Solution #0 (58026, time = 0 ms, branches = 0, failures = 0, depth = 0, memory used = 35.71 MB)
I0000 00:00:1698048441.895346    8204 search.cc:276] Finished search tree (time = 0 ms, branches = 0, failures = 1, memory used = 35.78 MB)
I0000 00:00:1698048441.895460    8204 search.cc:276] End search (time = 1 ms, branches = 0, failures = 1, memory used = 35.80 MB, speed = 0 branches/s)
I0000 00:00:1698048441.895694    8204 search.cc:276] Start search (memory used = 35.81 MB)
I0000 00:00:1698048441.895813    8204 search.cc:276] Root node processed (time = 0 ms, constraints = 279, memory used = 35.81 MB)
I0000 00:00:1698048441.895996    8204 search.cc:276] Solution #1 (58026, time = 0 ms, branches = 33, failures = 1, depth = 33, memory used = 35.84 MB, limit = 0%)    
I0000 00:00:1698048441.907753    8204 search.cc:276] Solution #2 (56508, maximum = 58026, time = 12 ms, branches = 37, failures = 3, depth = 33, MakePairActive, neighbors = 7829, filtered neighbors = 1, accepted neighbors = 1, memory used = 36.04 MB, limit = 1%)

```

Thank you!

Best Johannes

[Rummel]

A colleague run the script and got a result with the following output:

```
## Done

<bound method Solver.Parameters of <ortools.constraint_solver.pywrapcp.Solver; proxy of <Swig Object of type 'operations_research::Solver *' at 0x000001622FADE040> >>
WARNING: Logging before InitGoogleLogging() is written to STDERR
I1106 09:03:03.241236 11632 search.cc:265] Start search (memory used = 34.88 MB)
I1106 09:03:03.241800 11632 search.cc:265] Root node processed (time = 0 ms, constraints = 279, memory used = 35.11 MB)
I1106 09:03:03.242231 11632 search.cc:265] Solution #0 (58026, time = 0 ms, branches = 0, failures = 0, depth = 0, memory used = 35.22 MB)
I1106 09:03:03.242482 11632 search.cc:265] Finished search tree (time = 0 ms, branches = 0, failures = 1, memory used = 35.28 MB)
I1106 09:03:03.242638 11632 search.cc:265] End search (time = 1 ms, branches = 0, failures = 1, memory used = 35.30 MB, speed = 0 branches/s)
I1106 09:03:03.242970 11632 search.cc:265] Start search (memory used = 35.34 MB)
I1106 09:03:03.243281 11632 search.cc:265] Root node processed (time = 0 ms, constraints = 279, memory used = 35.34 MB)
I1106 09:03:03.243583 11632 search.cc:265] Solution #1 (58026, time = 0 ms, branches = 33, failures = 1, depth = 33, memory used = 35.34 MB, limit = 0%)
I1106 09:03:03.256380 11632 search.cc:265] Solution #2 (56508, objective maximum = 58026, time = 13 ms, branches = 37, failures = 3, depth = 33, MakePairActive, neighbors = 7829, filtered neighbors = 1, accepted neighbors = 1, memory used = 35.52 MB, limit = 1%)
I1106 09:03:03.258111 11632 search.cc:265] Solution #3 (56336, objective maximum = 58026, time = 14 ms, branches = 42, failures = 5, depth = 33, PairRelocateOperator, neighbors = 7832, filtered neighbors = 2, accepted neighbors = 2, memory used = 35.53 MB, limit = 1%)
I1106 09:03:03.258532 11632 search.cc:265] Solution #4 (52735, objective maximum = 58026, time = 15 ms, branches = 46, failures = 7, depth = 33, PairRelocateOperator, neighbors = 7837, filtered neighbors = 3, accepted neighbors = 3, memory used = 35.53 MB, limit = 1%)
I1106 09:03:03.258815 11632 search.cc:265] Solution #5 (51170, objective maximum = 58026, time = 15 ms, branches = 52, failures = 9, depth = 33, PairRelocateOperator, neighbors = 7843, filtered neighbors = 4, accepted neighbors = 4, memory used = 35.53 MB, limit = 1%)
I1106 09:03:03.259097 11632 search.cc:265] Solution #6 (50517, objective maximum = 58026, time = 15 ms, branches = 56, failures = 11, depth = 33, PairRelocateOperator, neighbors = 7867, filtered neighbors = 5, accepted neighbors = 5, memory used = 35.53 MB, limit = 1%)
I1106 09:03:03.259971 11632 search.cc:265] Solution #7 (50330, objective maximum = 58026, time = 16 ms, branches = 61, failures = 13, depth = 33, PairRelocateOperator, neighbors = 8484, filtered neighbors = 6, accepted neighbors = 6, memory used = 35.53 MB, limit = 1%)
I1106 09:03:03.274951 11632 search.cc:265] Solution #8 (47855, objective maximum = 58026, time = 31 ms, branches = 65, failures = 15, depth = 33, HeuristicPathLNS(GlobalCheapestInsertion), neighbors = 17543, filtered neighbors = 7, accepted neighbors = 7, memory used = 35.76 MB, limit = 3%)
I1106 09:03:03.279972 11632 search.cc:265] Solution #9 (47175, objective maximum = 58026, time = 36 ms, branches = 72, failures = 17, depth = 33, PairRelocateOperator, neighbors = 17982, filtered neighbors = 8, accepted neighbors = 8, memory used = 35.79 MB, limit = 3%)
I1106 09:03:03.285826 11632 search.cc:265] Solution #10 (46829, objective maximum = 58026, time = 42 ms, branches = 76, failures = 19, depth = 33, Relocate<1>, neighbors = 22949, filtered neighbors = 9, accepted neighbors = 9, memory used = 35.79 MB, limit = 4%)
I1106 09:03:03.304281 11632 search.cc:265] Finished search tree (time = 61 ms, branches = 111, failures = 54, neighbors = 33648, filtered neighbors = 9, accepted neigbors = 9, memory used = 35.79 MB)
I1106 09:03:03.304582 11632 search.cc:265] End search (time = 61 ms, branches = 111, failures = 54, memory used = 35.79 MB, speed = 1819 branches/s)
solution found
```

Does anyone have any idea why he gets a solution so quickly and I don't?

[Rummel]

We used different versions of OR-Tools. With version 9.5 a solution is found, with versions 9.6 and 9.7 the program does not terminate. The release notes of version 9.6 state that there are "Routing: Performance improvements (local search)". I am going to post that on github.

[Mizux Seiha]

ref: https://github.com/google/or-tools/issues/3975

Seem the commit https://github.com/google/or-tools/commit/1505af56efef0de2a4ff57e02ab896bbdb7935e6 introducing the new operator (default true)
local_search_operators.use_shortest_path_swap_active (id 34) make the solver hang.

As a workaround you can use this code to disable it.
```python
search_parameters.local_search_operators.use_shortest_path_swap_active = "BOOL_FALSE"
```