d-krupke/close-enough-tsp

Initial root node order by non implicite dics on the convex hull

barakugav opened this issue · 1 comments

Start by computing the convex hull, which implay a specific order T on the convex hull vertices.
We know T must be part of an optimal solution, but including all the hull vertices increase the branching factor of the B2B search significantly.
Instead of adding the complete order T, first compute an optimal solution only on the order T, remove the discs which are implicitly covered, and the remaining vertices are the initial root node order

Done some time ago