Seminario Interdipartimentale di Algoritmica
 
 

DIS - Dipartimento di Informatica e Sistemistica, via Salaria 113
Aula C2, piano secondo

Abstract:
The transportation problem (TP) is a classic problem in operations research. The problem was posed for the first time by Hitchcock in 1941 [Hitchcock, 1941] and independently by Koopmans in 1947 [Koopmans, 1948], and appears in any standard introductory course on operations research. The m\times n TP has~ m supply points and~ n demand points. Each supply point i holds a quantity r_i>0 , and each demand point j wants a quantity c_j>0 , with \sum \limits_{i=1}^m r_i = \sum \limits_{j=1}^n c_j . A solution to the problem can be written as a m\times n matrix X with entries decision variables x_{ij} having value equal to the amount transported from supply point i to demand point j . The objective is to minimize total transportation costs \sum\limits_{i=1}^m\sum\limits_{j=1}^n t_{ij} x_{ij} , where t_{ij} is the unit transportation cost from supply point i to demand point j . The set of feasible solutions of TP, is called the transportation polytope. The 1-skeleton (edge graph) of this polytope is defined as the graph with vertices the vertices of the polytope and edges its 1-dimensional faces. In 1957 W.M. Hirsch stated his famous conjecture (cf. [Dantzig, 1963]) saying that any d -dimensional polytope with n facets has diameter at most n-d . So far the best bound for any polytope is O(n^{\log d+1}) [Kalai and Kleitman, 1992]. Any strongly polynomial bound is still lacking. Such bounds have been proved for some special classes of polytopes (for examples, see [Schrijver, 1995]). Among those are some special classes of transportation polytopes [Balinski, 1974], [Bolker, 1972] and the polytope of the dual of TP [Balinski, 1974]. The first strongly polynomial bound on the diameter of the transportation polytope was given by Dyer and Frieze [DyerFrieze, 1994]. Actually, they prove a bound on the diameter of any polytope \{x\in\R^n\mid Ax\leq b,\ b\in\R^m\} where A is a totally unimodular matrix. The proof is complicated and indirect, using the probabilistic method. Moreover, the bound is huge ( O(m^{16}n3(\ln(mn))3) assuming m\leq n ). We will give a simple proof that the diameter of the transportation polytope is less than 8(m+n-2) . The proof is constructive: it gives an algorithm that describes how to go from any vertex to any other vertex on the transportation polytope in less than 8(m+n-2) steps along the edges.