liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A note on relatives to the Held and Karp 1-tree problem
Linköpings universitet, Matematiska institutionen. Linköpings universitet, Tekniska högskolan.
Linköpings universitet, Matematiska institutionen. Linköpings universitet, Tekniska högskolan.
Linköpings universitet, Matematiska institutionen. Linköpings universitet, Tekniska högskolan.ORCID-id: 0000-0003-2094-7376
2006 (Engelska)Ingår i: Operations Research Letters, ISSN 0167-6377, E-ISSN 1872-7468, Vol. 34, nr 3, s. 275-282Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We study a class of graph problems which includes as special cases the Held and Karp 1-tree problem, and the minimum spanning tree problem with one degree constraint studied by Glover and Klingman. For another special case, we note a mistake in a paper by Ramesh, Yoon and Karwan.

Ort, förlag, år, upplaga, sidor
2006. Vol. 34, nr 3, s. 275-282
Nationell ämneskategori
Matematik
Identifikatorer
URN: urn:nbn:se:liu:diva-36273DOI: 10.1016/j.orl.2005.04.010Lokalt ID: 30783OAI: oai:DiVA.org:liu-36273DiVA, id: diva2:257121
Tillgänglig från: 2009-10-10 Skapad: 2009-10-10 Senast uppdaterad: 2017-12-13
Ingår i avhandling
1. Accelerating column generation schemes: applications to routing problems
Öppna denna publikation i ny flik eller fönster >>Accelerating column generation schemes: applications to routing problems
2005 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
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.

Ort, förlag, år, upplaga, sidor
Linköping: Linköpings universitet, 2005. s. 34
Serie
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 978
Nationell ämneskategori
Matematik
Identifikatorer
urn:nbn:se:liu:diva-30273 (URN)15790 (Lokalt ID)91-85457-50-7 (ISBN)15790 (Arkivnummer)15790 (OAI)
Disputation
2005-11-28, Glashuset, Hus B, Campus Valla, Linköping, 10:15 (Svenska)
Opponent
Tillgänglig från: 2009-10-09 Skapad: 2009-10-09 Senast uppdaterad: 2012-12-06

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

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

Sök vidare i DiVA

Av författaren/redaktören
Westerlund, AndreasGöthe-Lundgren, MaudLarsson, Torbjörn
Av organisationen
Matematiska institutionenTekniska högskolan
I samma tidskrift
Operations Research Letters
Matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 396 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf