An improved variant of the Iterated Inside Out algorithm for solving the optimal transport DOTmark instances

The transportation problem has recently gained renewed interest due to its applications in machine learning and artificial intelligence, particularly in measuring distances between images. A novel exact algorithm for the transportation problem, called Iterated Inside Out, was recently proposed showing superior performances with respect to the relevant literature. In this paper, we present an improved version of Iterated Inside Out tailored for image processing instances. The algorithm relies on an improved search of negative reduced cost variables embedded into a Matryoshka approach for computing heuristic high-quality initial solutions. We show the superiority of our algorithm against the algorithms in the literature on the DOTmark dataset, a benchmark for image processing and large-scale transportation problems.