  We propose a novel exact algorithm for the transportation problem, one of the
paradigmatic network optimization problems. The algorithm, denoted Iterated
Inside Out, requires in input a basic feasible solution and is composed by two
main phases that are iteratively repeated until an optimal basic feasible
solution is reached. In the first "inside" phase, the algorithm progressively
improves upon a given basic solution by increasing the value of several
non-basic variables with negative reduced cost. This phase typically outputs a
non-basic feasible solution interior to the constraints 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.
