Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aoki S., Takemura A.: Minimal basis for connected Markov chain over 3 × 3 × K contingency tables with fixed two-dimensional marginals. Aust. N. Z. J. Stat. 45, 229–249 (2003)
Berstein Y., Onn S.: The Graver complexity of integer programming. Ann. Comb. 13, 289–296 (2009)
De Loera J., Hemmecke R., Onn S., Weismantel R.: N-fold integer programming. Disc. Optim. 5, 231–241 (2008) (volume in memory of George B. Dantzig)
De Loera J., Hemmecke R., Onn S., Rothblum U.G., Weismantel R.: Convex integer maximization via Graver bases. J. Pure Appl. Algebra 213, 1569–1577 (2009)
De Loera J., Onn S.: The complexity of three-way statisticaltables. SIAM J. Comp. 33, 819–836 (2004)
De Loera J., Onn S.: All linear and integer programs are slim 3-way transportation programs. SIAM J. Optim. 17, 806–821 (2006)
De Loera J., Onn S.: Markov bases of three-way tables are arbitrarily complicated. J. Symb. Comp. 41, 173–181 (2006)
Graver J.E.: On the foundation of linear and integer programming I. Math. Prog. 9, 207–226 (1975)
Hemmecke, R., Onn, S., Weismantel, R.: A polynomial oracle-time algorithm for convex integer minimization. Math. Prog. (To appear)
Hoffman, A.J., Kruskal, J.B.: Integral boundary points of convex polyhedra. In: Linear Inequalities and Related Systems. Ann. Math. Stud., vol. 38, pp. 223–246. Princeton University Press, Princeton (1956)
Hoşten S., Sullivant S.: Finiteness theorems for Markov bases of hierarchical models. J. Comb. Theory Ser. A 114, 311–321 (2007)
Leighton T., Rao S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. Assoc. Comp. Mach. 46, 787–832 (1999)
Lenstra H.W. Jr: Integer programming with a fixed number ofvariables. Math. Oper. Res. 8, 538–548 (1983)
Santos F., Sturmfels B.: Higher Lawrence configurations. J. Comb. Theory Ser. A 103, 151–164 (2003)
Schrijver A.: Theory of Linear and Integer Programming. Wiley, Chichester (1986)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hemmecke, R., Onn, S. & Weismantel, R. N-fold integer programming and nonlinear multi-transshipment. Optim Lett 5, 13–25 (2011). https://doi.org/10.1007/s11590-010-0231-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-010-0231-9