The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation

Yixin Zhao (), Torbjörn Larsson (), Elina Rönnberg () and Panos M. Pardalos ()
Additional contact information
Yixin Zhao: Nanjing University of Science and Technology
Torbjörn Larsson: Linköping University
Elina Rönnberg: Linköping University
Panos M. Pardalos: University of Florida

Journal of Global Optimization, 2018, vol. 72, issue 3, No 7, 517-538

Abstract: Abstract 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 $$l_1$$ l 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.

Keywords: Fixed charge transportation problem; Lagrangian decomposition; Column generation; Regularization; Core problem; 90B06; 90C08; 90C11; 90C59 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-018-0661-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:72:y:2018:i:3:d:10.1007_s10898-018-0661-y

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-018-0661-y

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().