TSP local search loops indefinitely on instance with different start and end

[jcoupey]

I have a randomly generated problem instance with TSPLIB-like rounded costs that triggers an infinite loop on current master. This happens right after clustering, during the TSP solving for the first cluster.

Detailed output log shows

[...]
[TSP] Start local search on asymmetric problem using 1 thread(s).
* Performed 1 "avoid loop" steps, gaining 1073741871.
* Performed 1 "2-opt" steps, gaining 3221225425.
* Performed 1 "avoid loop" steps, gaining 1073741871.
* Performed 1 "2-opt" steps, gaining 3221225425.
[...]

It is normal behaviour to go through the local search phase for an asymmetric problem because we've messed with the matrix values to account for the different start and end.

My first guess is that the avoid loop move wrongly thinks it's a good idea to break the (virtual) end -> start edge whose cost has been purposely set to zero, then a 2-opt move fixes it back.

[jcoupey]

So what happens is that there is a relocatable chain consisting of the start and the first job.

What the avoid loop step does is try to move that after the second job, so we go from e->s->j1->j2->j3 to e->j2->j1->s->j3.
e->s is set to cost zero. But while we evaluate the cost before and after the move, we encounter e->j1 and e->j2 whose cost is set to INFINITE_COST = 3 * (std::numeric_limits<cost_t>::max() / 4) in order to prevent those edges to be included in the first place. Because of the before_cost and after_cost overflowing the uint32_t max value, this comparison is meaningless.

[jcoupey]

The reason why this did not show up before is that we need to have both a start and an end and make them different. Then there must be a relocatable chain that includes the start and at least another point. This is the case with the above example where the cost rounding also helps...

Simple fix: make sure that the start in never included in a relocatable chain in this situation.