A branch-cut-and-price algorithm for the piecewise linear transportation problem

In this paper we present an exact solution method for the transportation problem with piecewise linear costs. This problem is fundamental within supply chain management and is a straightforward extension of the fixed-charge transportation problem. We consider two Dantzig-Wolfe reformulations and investigate their relative strength with respect to the linear programming (LP) relaxation, both theoretical and practical, through tests on a number of instances. Based on one of the proposed formulations we derive an exact method by branching and adding generalized upper bound constraints from violated cover inequalities. The proposed solution method is tested on a set of randomly generated instances and compares favorably to solving the model using a standard formulation solved by a state-of-the-art commercial solver.