Fixed-Charge Transportation Problem: Facets of the Projection Polyhedron

Yogesh Agarwal () and Yash Aneja ()
Additional contact information
Yogesh Agarwal: Indian Institute of Management, Lucknow 226 013, Uttar Pradesh, India
Yash Aneja: Odette School of Business, University of Windsor, Windsor, Ontario N9B 3P4, Canada

Operations Research, 2012, vol. 60, issue 3, 638-654

Abstract: In this paper we consider the well-known fixed-charge transportation problem. To send any flow from source s i to destination t j , we incur a unit variable shipping cost of c ij and a fixed cost f ij . Here we study the structure of the projection polyhedron of this problem, in the space of 0-1 variables associated with fixed charges, and we develop several classes of valid inequalities and derive conditions under which they are facet defining. In some cases, if the conditions are not satisfied, we show how they can be lifted to define facets. Several heuristics for generating and adding these facets are presented. Using these results, we develop a computationally effective algorithm for solving the problem. The computational results clearly indicate the usefulness of this approach.

Keywords: fixed charge; transportation problem; integer programming; branch and cut (search for similar items in EconPapers)
Date: 2012
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/opre.1120.1041 (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:oropre:v:60:y:2012:i:3:p:638-654

Access Statistics for this article

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