Seminar announcement: Prof. Federico Della Croce (PoliTo) @ UniPv and on Zoom, Dec 16th, 15:00
5 views
Skip to first unread message
david...@unipv.it
Dec 13, 2025, 6:15:35 AM12/13/25
to AIROYoung Researchers
Dear AiroYoungers,
On Tuesday, December 16th, at 15:00, Prof. Federico Della Croce (Full Professor at Politecnico di Torino) will give a seminar on recent advances in combinatorial optimization and network flow problems, presenting joint work with R. Bargetto and R. Scatamacchia.
The title of the talk is:
“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.
The seminar is organized by the Department of Mathematics “Felice Casorati” and will be held in the IMATI-CNR Conference Room at the University of Pavia.
For those interested, the seminar will also be streamed on Zoom:
https://unipv-it.zoom.us/j/91498434319?pwd=uQV55z8RYiC4h8vL97CAWKBMgBazva.1
Kind regards,
Davide Duma
On Tuesday, December 16th, at 15:00, Prof. Federico Della Croce (Full Professor at Politecnico di Torino) will give a seminar on recent advances in combinatorial optimization and network flow problems, presenting joint work with R. Bargetto and R. Scatamacchia.
The title of the talk is:
“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.
The seminar is organized by the Department of Mathematics “Felice Casorati” and will be held in the IMATI-CNR Conference Room at the University of Pavia.
For those interested, the seminar will also be streamed on Zoom:
https://unipv-it.zoom.us/j/91498434319?pwd=uQV55z8RYiC4h8vL97CAWKBMgBazva.1
Kind regards,
Davide Duma
Reply all
Reply to author
Forward
0 new messages