N‐fold integer programming and nonlinear multi‐transshipment

The multi‐transshipment problem is NP‐hard already for two commodities over bipartite networks. Nonetheless, using our recent theory of n‐fold integer programming and extensions developed herein, we are able to establish the polynomial time solvability of the problem in two broad situations. First, for any fixed number of commodities and number of suppliers, we solve the problem over bipartite networks with variable number of consumers in polynomial time. This is very natural in operations research applications where few facilities serve many customers. Second, for every fixed network, we solve the problem with variable number of commodities in polynomial time.