Exponential irreducible neighborhoods for combinatorial optimization problems |
| |
Authors: | Robert T Firla Bianca Spille Robert Weismantel |
| |
Institution: | 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 Department of Mathematics, EPFL-DMA, CH-1015 Lausanne, Switzerland (e-mail: bianca.spille@epfl.ch), CH
|
| |
Abstract: | 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. |
| |
Keywords: | : exponential neighborhoods irreducible augmentation vectors alternating paths and cycles TSP Sequential Ordering Problem |
本文献已被 SpringerLink 等数据库收录! |
|