Abstract:
A three-way transportation polytope consists of nonnegative three-way arrays with prescribed sums along every coordinate line. We show that its geometry and the difficulty of finding its integer points are both controlled by one local quantity: the number of cells on a line that can be positive. The change happens between two and three. The slim construction passes through fractional perfect matchings of hypergraphs and places each hyperedge on a cycle of six cells. If every line has at most two such cells, every nonempty polytope is a product of intervals, and integer feasibility is solvable in polynomial time for integral line sums. If lines of one direction may have three, every nonempty rational polytope is rationally affinely isomorphic to an entire polytope of format 3×c×h with line sums in {0,1,2}, and integer feasibility is NP-complete. Hardness persists when the input includes a feasible array that is positive on every cell that can be positive and takes only the values 1/3 and 2/3 there. Unless P = NP, solving the linear relaxation and knowing its support does not help to round it. With all line sums equal to one, as in the linear relaxation of planar three-index assignment, the threshold becomes three cells in every direction. In this case the vertices have arbitrarily large denominators: every denominator m ≥ 2 occurs with O(log m) fractional entries in arrays of order O(√log m), and both bounds are optimal up to constant factors. The slim class with line sums in {0,1,2} is universal for linear programming.