[Dottorcomp] Seminari di Matematica Applicata, 16/12/2025, Federico Della Croce

[Stefano Lisini]

Seminari di Matematica Applicata, Dipartimento di Matematica "F. Casorati"
e Istituto del CNR IMATI "E. Magenes" di Pavia.

Martedì 16 Dicembre 2025, *alle ore 15* precise, presso la sala conferenze
dell'IMATI-CNR di Pavia

Federico Della Croce (Politecnico di Torino)

terrà un seminario dal titolo:

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

Abstract: 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 computed. 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 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 commercial solvers
such as Cplex and Gurobi and other exact algorithms available in the
literature.

The interest in the transportation problem has been renewed recently
because of machine learning and artificial intelligence applications
requiring the computation of the distance between pairs of images with
source and destination quantities being pixel intensities. A set of image
processing instances, called DOTmark, is nowadays the benchmark for this
problem. We show that also for these instances a tailored version of IIO
exploiting a Matryoshka approach and relying on an improved search of
negative reduced cost variables strongly dominates the relevant literature
and solves to optimality for the first time instances with up 2^36
variables.

Joint work with R. Bargetto and R. Scatamacchia

-----------------------------------------
https://matematica.unipv.it/ricerca/cicli-di-seminari/seminari-di-matematica-applicata/