Fixed-charge transportation on a path: optimization, LP formulations and separation
AbstractThe 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) in its series CORE Discussion Papers with number 2010068.
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
mixed-integer programming; lot-sizing; transportation; convex hull; extended formulation;
This paper has been announced in the following NEP Reports:
You can help add them by filling out this form.
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.