EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1010. An improved variant of the Iterated Inside Out algorithm for solving the optimal transport DOTmark Instances

Invited abstract in session MD-26: Optimization problems on graphs, stream Combinatorial Optimization.

Monday, 14:30-16:00
Room: 012 (building: 208)

Authors (first author is the speaker)

1. Federico Della Croce
DIGEP, Politecnico di Torino
2. Roberto Bargetto
3. Rosario Scatamacchia
DIGEP, Politecnico di Torino

Abstract

The optimal transport (OT) is a paradigmatic network problem and consists in finding the minimum cost transportation plan that moves quantities of a single item from a set of sources to a set of destinations, where, for each pair source/destination (i,j), a unit transportation cost holds. The interest in OT has been renewed lately in artificial intelligence applications where a set of instances, called DOTmark, is nowadays the benchmark for OT. Recently, a new exact algorithm for solving OT, called iterated Inside Out (IIO), has been proposed. The strength of this method relies on the fact that potentially many pivoting operations are performed for each computation of dual multipliers and reduced costs. Here, we propose a variant of IIO specifically tailored to the DOTmark instances. This variant solves these instances exploiting the peculiar structure of the transportation costs: these costs depend on the couple of indexes (i,j) of the related variables and present strong regularity in the way they increase or decrease according to a change of index i or j. Given a basic solution, the described structure of costs enables the algorithm to predict from scratch the positivity of a huge set of reduced costs, thus avoiding their computation. Also, it enables to detect the presence of non basic variables with negative reduced costs within a reduced subset of variables. Computational results indicate that this approach is largely superior to the current state of the art algorithms.

Keywords

Status: accepted


Back to the list of papers