The Fixed Charge Transportation Problem: An Exact Algorithm Based on a New Integer Programming Formulation

Roberto Roberti (), Enrico Bartolini () and Aristide Mingozzi ()
Additional contact information
Roberto Roberti: Department of Electrical, Electronic, and Information Engineering “Guglielmo Marconi” (DEI), University of Bologna, 40126 Bologna, Italy
Enrico Bartolini: Department of Mathematics and Systems Analysis, Aalto University School of Science, 00076 Aalto, Finland
Aristide Mingozzi: Department of Mathematics, University of Bologna, 40126 Bologna, Italy

Management Science, 2015, vol. 61, issue 6, 1275-1291

Abstract: The fixed charge transportation problem generalizes the well-known transportation problem where the cost of sending goods from a source to a sink is composed of a fixed cost and a continuous cost proportional to the amount of goods sent. In this paper, we describe a new integer programming formulation with exponentially many variables corresponding to all possible flow patterns to sinks. We show that the linear relaxation of the new formulation is tighter than that of the standard mixed integer programming formulation. We describe different classes of valid inequalities for the new formulation and a column generation method to compute a valid lower bound embedded into an exact branch-and-price algorithm. Computational results on test problems from the literature show that the new algorithm outperforms the state-of-the-art exact methods from the literature and can solve instances with up to 70 sources and 70 sinks.Data, as supplemental material, are available at http://dx.doi.org/10.1287/mnsc.2014.1947 . This paper was accepted by Dimitris Bertsimas, optimization .

Keywords: transportation; fixed charge; column generation (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2014.1947 (application/pdf)

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:inm:ormnsc:v:61:y:2015:i:6:p:1275-1291

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().