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
The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation
Nanjing University of Science and Technology, School of Automation.
Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0003-2094-7376
Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-2081-2888
University of Florida, Department of Industrial and System Engineering.
2018 (English)In: Journal of Global Optimization, ISSN 0925-5001, E-ISSN 1573-2916, Vol. 72, no 3, p. 517-538Article in journal (Refereed) Published
Abstract [en]

A new and strong convexified formulation of the fixed charge transportation problem is provided. This formulation is obtained by integrating the concepts of Lagrangian decomposition and column generation. The decomposition is made by splitting the shipping variables into supply and demand side copies, while the columns correspond to extreme flow patterns for single sources or sinks. It is shown that the combination of Lagrangian decomposition and column generation provides a formulation whose strength dominates those of three other convexified formulations of the problem. Numerical results illustrate that our integrated approach has the ability to provide strong lower bounds. The Lagrangian decomposition yields a dual problem with an unbounded set of optimal solutions. We propose a regularized column generation scheme which prioritizes an optimal dual solution with a small 1-norm. We further demonstrate numerically that information gained from the strong formulation can also be used for constructing a small-sized core problem which yields high-quality upper bounds.

Place, publisher, year, edition, pages
Springer Publishing Company, 2018. Vol. 72, no 3, p. 517-538
Keywords [en]
Fixed charge transportation problem, Lagrangian decomposition, Column generation, Regularization, Core problem
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-148914DOI: 10.1007/s10898-018-0661-yISI: 000448280900007OAI: oai:DiVA.org:liu-148914DiVA, id: diva2:1222528
Note

Funding agencies: 1035 Equipment Pre-Research Field Foundation of China [61403120401]; Fundamental Research Funds for the Central Universities [30918011333]; Center for Industrial Information Technology (CENIIT) at Linkoping University [16.05]

Available from: 2018-06-21 Created: 2018-06-21 Last updated: 2018-11-09

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

By author/editor
Larsson, TorbjörnRönnberg, Elina
By organisation
Optimization Faculty of Science & Engineering
In the same journal
Journal of Global Optimization
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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