Fixed-charge Transportation On A Path: Optimization, LP Formulations And Separation

Date Added: Oct 2010
Format: PDF

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. The authors then provide a polyhedral analysis of the polynomially solvable special case in which the associated bipartite graph is a path. They describe a new class of inequalities that they call "Path-modular" inequalities. They 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.