Exponential irreducible neighborhoods for combinatorial optimization problems

This paper deals with irreducible augmentation vectors associated with three combinatorial optimization problems: the TSP, the ATSP, and the SOP. 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 a families of facet inducing inequalities.

Authors and Affiliations

1. Institute for Mathematical Optimization, Otto-von-Guericke-University Magdeburg, Universitätsplatz 2, D-39106 Magdeburg, Germany (e-mail: [firla,weismantel]@imo.math.uni-magdeburg.de), , , , , , DE

   Robert T. Firla & Robert Weismantel

2. Department of Mathematics, EPFL-DMA, CH-1015 Lausanne, Switzerland (e-mail: bianca.spille@epfl.ch), , , , , , CH

   Bianca Spille

Reprints and permissions