On the Diameter of the Transportation Polytope

Jan van den Heuvel

London School of Economics

Abstract

The transportation problem (TP) is a classic problem in operations research. The m&nbsp;x&nbsp;n TP has m supply points and n demand points. Each supply point i holds a quantity r_i, and each demand point j wants a quantity c_j, where the total supply is equal to the total demand. Suppose we must transport non-negative quantities x_ij from nodes i to j so that all demands are met. The collection of all feasible solutions forms a convex polytope, the transportation polytope T.<br> We are interested in the diameter of the skeleton (the edge-graph) of T. In the talk I give some motivation why this is an interesting problem. We also show how the problem to find the diameter can be formulated completely in terms of operations on subgraphs of edge-weighted