How the Search Tree branches in routing solver?

[FirstPotatoOnMars]

Hi, I am really interested in the search tree of the routing solver. I know that in exact algorithms, the branch and bound works based on a search tree and can branch on variables or constraints.
And my question is how search tree works in this routing solver, and how it branches? As I know the algorithm of the routing solver is mainly based on meta-heuristics (if I understand the solver right)? I would be very grateful if someone can help me answer this !

Start search (memory used = 205.35 MB)
Root node processed (time = 0 ms, constraints = 197, memory used = 205.35 MB)
Solution #0 (261798, time = 0 ms, branches = 0, failures = 0, depth = 0, memory used = 205.35 MB)
Finished search tree (time = 0 ms, branches = 0, failures = 1, memory used = 205.35 MB)
End search (time = 1 ms, branches = 0, failures = 1, memory used = 205.35 MB, speed = 0 branches/s)

[lperron]

it does not branch. Local search is implemented inside the tree search with hacks.

[FirstPotatoOnMars]

Thanks a lot for answering me!

I still have the following question: what is each of the branches of search tree means? Is each one a solution?

Because I notice that the value of branches and neighbors grows with the solving process. What is the difference between branches and neighbors? What exactly do these two referring to?

[lperron]

not exactly. As far as I remember, the solver builds a balanced binary search tree where each leaf is a solution. Branches should be the number of branches explored in the balanced search tree. But just ignore it, it is irrelevant. They are just a tool used to implement the LS. Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le jeu. 10 oct. 2024 à 15:19, FirstPotatoOnMars ***@***.***> a écrit :

…

Thanks a lot for answering me! I still have the following question: what is each of the *branches* of search tree means? Is each one a solution? Because I notice that the value of *branches* and *neighbors* grows with the solving process. What is the difference between *branches* and *neighbors*? What exactly do these two referring to? — Reply to this email directly, view it on GitHub <#4409 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3PMY2HIPOBAY4X77UTZ2Z5HPAVCNFSM6AAAAABPWWBFJ6VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTAOJQGQZDQNQ> . You are receiving this because you modified the open/close state.Message ID: ***@***.***>

[FirstPotatoOnMars]

I see.. Thanks for your reply!