subtour

plural subtours

1. graph theoryA tour that makes up part of a larger tour.

   The resulting problem is solved to integer optimality, violated constraints (which are trivial to find) are added and the process is repeated until a feasible solution is found. In order to speed up the algorithm we pursue several attempts to find as many relevant subtours as possible.

   2015, Ulrich Pferschy, Rostislav Stanek, “Generating subtour elimination constraints for the TSP from pure integer solutions”, in arXiv