EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
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:00Room: 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
- Transportation
- Combinatorial Optimization
Status: accepted
Back to the list of papers