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.