Exponential irreducible neighborhoods for combinatorial optimisation problems

This paper deals with irreducible augmentation vectors associated with three combinatorial optimization problems: the travelling salesman problem, the asymmetric travelling salesman problem, and the sequential ordering problem. We study families of irreducible vectors of exponential size, derived from alternating cycles, where optimizing a linear function over each of these families can be done in polynomial time. A family of irreducible vectors induces an irreducible neighborhood; an algorithm for optimizing over this family is known as a local search heuristic. Irreducible neighborhoods do not only serve as a tool to improve feasible solutions, but do play an important role in an exact primal algorithm; such families are the primal counterpart of families of facet inducing inequalities.