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
A stabilized column generation scheme for the traveling salesman subtour problem
Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.ORCID iD: 0000-0003-2094-7376
2006 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, Vol. 154, no 15, 2212-2238 p.Article in journal (Refereed) Published
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 includes a depot vertex, satisfies a knapsack constraint on the vertex weights, and that minimizes edge costs minus vertex revenues along the subtour.

We propose a decomposition scheme for this problem. It is inspired by the classic side-constrained 1-tree formulation of the traveling salesman problem, and uses stabilized column generation for the solution of the linear programming relaxation. Further, this decomposition procedure is combined with the addition of variable upper bound (VUB) constraints, which improves the linear programming bound. Furthermore, we present a heuristic procedure for finding feasible subtours from solutions to the column generation problems. An extensive experimental analysis of the behavior of the computational scheme is presented.

Place, publisher, year, edition, pages
2006. Vol. 154, no 15, 2212-2238 p.
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-36277DOI: 10.1016/j.dam.2005.04.012Local ID: 30825OAI: oai:DiVA.org:liu-36277DiVA: diva2:257125
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2013-08-30
In thesis
1. Accelerating column generation schemes: applications to routing problems
Open this publication in new window or tab >>Accelerating column generation schemes: applications to routing problems
2005 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Many integer optimization problems of great practical importance are today attacked with column generation. Merits of column generation is that it enables the use of compact and flexible formulations of many complex optimization problems, and that it often gives rise to good (strong) formulations. A potential drawback with column generation is the well-known tailing-off phenomenon, that is, that the objective value is improved rapidly in early iterations but very slowly in the late iterations.

We study various techniques for accelerating column generation methods for (integer) linear programs. We evaluate the use of stabilized column generation on a Traveling Salesman Subtour Problem, TSSP, a problem which is closely related to the Prize Collecting Traveling Salesman Problem. We further study how subgradient optimization can be used with the purpose of predicting optimal columns (and, optionally, non-binding restrictions). This technique is tested on the TSSP and the multicommodity network flow problem.

Another idea evaluated in this thesis is the use of over-generation of columns in a column generation scheme for an integer programming problem, in this case a vehicle routing problem with a heterogeneous fleet of vehicles.

The thesis also includes a note on a class of relatives to the Held and Karp 1–tree problem. It is shown that two subclasses have polynomial time-complexity. Further, we note a mistake in an earlier work and provide a counter-example to the erroneous result.

Place, publisher, year, edition, pages
Linköping: Linköpings universitet, 2005. 34 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 978
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-30273 (URN)15790 (Local ID)91-85457-50-7 (ISBN)15790 (Archive number)15790 (OAI)
Public defence
2005-11-28, Glashuset, Hus B, Campus Valla, Linköping, 10:15 (Swedish)
Opponent
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2012-12-06

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Westerlund, AndreasGöthe-Lundgren, MaudLarsson, Torbjörn

Search in DiVA

By author/editor
Westerlund, AndreasGöthe-Lundgren, MaudLarsson, Torbjörn
By organisation
Department of MathematicsThe Institute of Technology
In the same journal
Discrete Applied Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 392 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