Iterated Inside Out: A New Exact Algorithm for the Transportation Problem

We propose a novel exact algorithm for the transportation problem, one of the paradigmatic network optimization problems. The algorithm, called Iterated Inside Out, requires as input a basic feasible solution and is composed of two main phases that are iteratively repeated until an optimal basic feasible solution is computed. In the first “inside” phase, the algorithm progressively improves upon a given basic solution by increasing the value of several nonbasic variables with negative reduced cost. This phase typically outputs a nonbasic feasible solution interior to the constraint set polytope. The second “out” phase moves in the opposite direction by iteratively setting to zero several variables until a new improved basic feasible solution is reached. Extensive computational tests show that the proposed approach strongly outperforms all versions of network and linear programming algorithms available in the commercial solvers CPLEX and Gurobi and other exact algorithms available in the literature.