Fixed-charge transportation on a path: optimization, LP formulations and separation

Mathieu van Vyve ()
Additional contact information
Mathieu van Vyve: Université catholique de Louvain, CORE and Louvain School of Management, B-1348 Louvain-la-Neuve, Belgium

No 2010068, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: The fixed-charge transportation problem is an interesting problem in its own right. This paper further motivates its study by showing that it is both a special case and a strong relaxation of the big-bucket multi-item lot-sizing problem. We then provide a polyhedral analysis of the polynomially solvable special case in which the associated bipartite graph is a path. We give a O(n^3)-time optimization algorithm and two O(n^2)-size linear programming extended formulation. We describe a new class of inequalities that we call "path-modular" inequalities. We give two distinct proofs of their validity. The first one is direct and crucially relies on sub- and super- modularity of an associated set function. The second proof is by showing that the projection of one of the extended linear programming formulations onto the original variable space yields exactly the polyhedron described by the path- modular inequalities. Thus we also show that these inequalities suffice to describe the convex hull of the set of feasible solutions. We finally report on computational experiments comparing extended LP formulation, valid inequalities separation and a standard MIP solver.

Keywords: mixed-integer programming; lot-sizing; transportation; convex hull; extended formulation (search for similar items in EconPapers)
JEL-codes: C11 C35 Q25 (search for similar items in EconPapers)
Date: 2010-10-01
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2010.html (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:cor:louvco:2010068

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().