Exponential irreducible neighborhoods for combinatorial optimization problems

Robert T. Firla, Bianca Spille and Robert Weismantel

Mathematical Methods of Operations Research, 2002, vol. 56, issue 1, 29-44

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. Copyright Springer-Verlag Berlin Heidelberg 2002

Keywords: Key words: exponential neighborhoods; irreducible augmentation vectors; alternating paths and cycles; TSP; Sequential Ordering Problem (search for similar items in EconPapers)
Date: 2002
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s001860200198 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:56:y:2002:i:1:p:29-44

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s001860200198

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().