An Exact Algorithm for the Fixed Charge Transportation Problem Based on Matching Source and Sink Patterns

This paper describes an exact algorithm for the fixed charge transportation problem based on a new integer programming formulation that involves two sets of variables representing flow patterns from sources to sinks and from sinks to sources. The formulation states to select a pattern for each source and each sink and to match the corresponding flows. The linear relaxation of this new formulation is enforced by adding a pseudo-polynomial number of equations that are shown to contain, as special cases, different valid inequalities recently proposed for the problem. The resulting lower bound dominates the lower bounds proposed in the literature. Such a lower bound is embedded into an exact branch-and-cut-and-price algorithm. Computational results on benchmark instances show that the proposed algorithm is several times faster than the state-of-the-art exact methods and could solve all open instances. New harder instances with up to 120 sources and 120 sinks were solved to optimality