On February 7th, 2023 at 3.30 pm Federico Della Croce, Professor at DIGEP of Politecnico di Torino, will give a seminar on "ITERATED INSIDE-OUT: a new exact algorithm for the transportation problem" in DEIB Seminar Room.

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 the 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. Eventually, the algorithm stops once an optimal basic feasible solution is reached. Computational testing shows that the proposed approach strongly outperforms all versions of network and linear programming algorithms available in the commercial softwares CPLEX and GUROBI.
This is joint work with Roberto Bargetto and Rosario Scatamacchia.