Fixed-charge transportation on a path: optimization, LP formulations and separation
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.
|Date of creation:||01 Oct 2010|
|Date of revision:|
|Contact details of provider:|| Postal: Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium)|
Fax: +32 10474304
Web page: http://www.uclouvain.be/core
More information through EDIRC
When requesting a correction, please mention this item's handle: RePEc:cor:louvco:2010068. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Alain GILLIS)
If references are entirely missing, you can add them using this form.