liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Decomposition schemes for the traveling salesman subtour problem
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
2002 (English)Licentiate thesis, monograph (Other academic)
Abstract [en]

Given an undirected graph with edge costs and both revenues and weights on the vertices, the Traveling Salesman Subtour Problem is to find a subtour that passes a depot vertex, satisfies a knapsack constraint on the vertex weights, and that minimizes edge costs minus vertex revenues along the subtour. This problem generalizes the Traveling Salesman Problem and is therefore -hard. The Traveling Salesman Subtour Problem and its relatives are of interest in themselves, and they also arise as subproblems in various contexts.

We present a new and strong formulation, which is inspired by the classic side-constrained 1-tree formulation of the Traveling Salesman Problem. Here, the side constraints comprise vertex degree restrictions, a knapsack constraint and variable upper bound (VUB) constraints. In our solution approaches, these side constraints are Lagrangian relaxed. The relaxed problem is transformed, via a simple variable substitution, into the problem of finding a minimum cost degree-constrained 1-tree in an expanded graph.

The Lagrangian dual problem is attacked with subgradient optimization and a cutting plane scheme. The latter is implemented in its dually equivalent form, that is, as a column generation scheme. The column generation procedure is stabilized by restricting the dual variables to stay inside a box around the current dual iterate; this technique is a slight modification of the so called boxstep method. Further, a combined algorithm is presented. This combination inherits the advantages of subgradient optimization and column generation, and it aims to avoid their respective drawbacks.

An important conclusion from our work is that the use of the VUB constraints significantly improves the quality of the lower bounds, although they are redundant in the integer programming formulation. We also conclude that the stabilizing technique is crucial for obtaining computational efficiency in the column generation scheme. Finally, it is established that it might be very advantageous to use the subgradient optimization procedure as a means for initiating the column generation scheme.

Place, publisher, year, edition, pages
Linköping: Linköpings universitet , 2002. , p. 92
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 939
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-145977ISBN: 9173733199 (print)OAI: oai:DiVA.org:liu-145977DiVA, id: diva2:1194030
Presentation
2002-04-26, Schrödinger (E324), Fysikhuset, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Opponent
Available from: 2018-03-28 Created: 2018-03-28 Last updated: 2018-12-04Bibliographically approved

Open Access in DiVA

No full text in DiVA

Authority records BETA

Westerlund, Andreas

Search in DiVA

By author/editor
Westerlund, Andreas
By organisation
Optimization The Institute of Technology
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 9 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf