liu.seSearch for publications in DiVA
Change search

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 $\tiny\mathcal{N} \mathcal{P}$-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.

##### Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 939
Mathematics
##### Identifiers
ISBN: 9173733199 (print)OAI: oai:DiVA.org:liu-145977DiVA, id: diva2:1194030
##### 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

isbn
urn-nbn

#### Altmetric score

isbn
urn-nbn
Total: 9 hits

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