Skip to main content
SpringerLink
Log in

n-Fold integer programming in cubic time

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

n-Fold integer programming is a fundamental problem with a variety of natural applications in operations research and statistics. Moreover, it is universal and provides a new, variable-dimension, parametrization of all of integer programming. The fastest algorithm for n-fold integer programming predating the present article runs in time \({O \left(n^{g(A)}L\right)}\) with L the binary length of the numerical part of the input and g(A) the so-called Graver complexity of the bimatrix A defining the system. In this article we provide a drastic improvement and establish an algorithm which runs in time O (n 3 L) having cubic dependency on n regardless of the bimatrix A. Our algorithm works for separable convex piecewise affine objectives as well. Moreover, it can be used to define a hierarchy of approximations for any integer programming problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aoki S., Takemura A.: Minimal basis for connected Markov chain over 3 times 3 times K contingency tables with fixed two-dimensional marginals. Aust. New Zeal. J. Stat. 45, 229–249 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  2. Berstein Y., Onn S.: The Graver complexity of integer programming. Ann. Combin. 13, 289–296 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  3. Cook W., Fonlupt J., Schrijver A.: An integer analogue of Carathéodory’s theorem. J. Combin. Theory Ser. B 40, 63–70 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  4. 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)

    Article  MathSciNet  MATH  Google Scholar 

  5. De Loera J.A., Hemmecke R., Onn S., Weismantel R.: N-fold integer programming. Discret. Optim. 5, 231–241 (2008) (Volume in memory of George B. Dantzig)

    Article  MathSciNet  MATH  Google Scholar 

  6. De Loera J.A., Onn S.: All linear and integer programs are slim 3-way transportation programs. SIAM J. Optim. 17, 806–821 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  7. Dobra, A., Fienberg, S.E., Rinaldo, A., Slavković, A., Zhou, Y.: Algebraic statistics and contingency table problems: log-linear models, likelihood estimation, and disclosure limitation. In: Emerging Applications of Algebraic Geometry: IMA Volumes in Mathematics and its Applications, vol. 148, pp. 63–88. Springer (2009)

  8. Graver J.E.: On the foundation of linear and integer programming I. Math. Program. 9, 207–226 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  9. Hemmecke, R., Köppe, M., Weismantel, R.: A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs. In: IPCO, vol. 14 (2010)

  10. Hemmecke R., Onn S., Weismantel R.: A polynomial oracle-time algorithm for convex integer minimization. Math. Program. 126, 97–117 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  11. Hemmecke R., Onn S., Weismantel R.: N-fold integer programming and nonlinear multi-transshipment. Optim. Lett. 5, 13–25 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  12. Hemmecke R., Schultz R.: Decomposition of test sets in stochastic integer programming. Math. Program. 94, 323–341 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  13. Hoşten S., Sullivant S.: Finiteness theorems for Markov bases of hierarchical models. J. Combin. Theory Ser. A 114, 311–321 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  14. Kobayashi, Y., Murota, K., Weismantel, R.: Cone superadditivity of discrete convex functions. Math. Program. (to appear). doi:10.1007/s10107-011-0447-1

  15. Louveaux, F.V., Schultz, R.: Stochastic integer programming. In: Handbooks in Operations Research and Management Science, vol. 10 pp. 213–266. Elsevier (2003)

  16. Murota K., Saito H., Weismantel R.: Optimality criterion for a class of nonlinear integer programs. Oper. Res. Lett. 32, 468–472 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  17. Onn, S.: Nonlinear Discrete Optimization. Zurich Lectures in Advanced Mathematics. Eur. Math. Soc. x+137 pp. (September 2010)

  18. Santos F., Sturmfels B.: Higher Lawrence configurations. J. Combin. Theory Ser. A 103, 151–164 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  19. Sebö, A.: Hilbert Bases, Carathéodory’s Theorem and Combinatorial Optimization. pp. 431–607. vol. 1, Waterloo University Press, IPCO, Waterloo (1990)

  20. Slavković, A.B., Zhu, X., Petrović, S.: A sample space of k-way tables given conditionals and their relations to marginals: Implications for cell bounds and Markov bases. Preprint, 35 pp. (2009)

Download references

Author information

Authors and Affiliations

  1. Technische Universität Munich, Munich, Germany

    Raymond Hemmecke

  2. Technion, Israel Institute of Technology, Haifa, Israel

    Shmuel Onn & Lyubov Romanchuk

Authors
  1. Raymond Hemmecke
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shmuel Onn
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lyubov Romanchuk
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Raymond Hemmecke.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hemmecke, R., Onn, S. & Romanchuk, L. n-Fold integer programming in cubic time. Math. Program. 137, 325–341 (2013). https://doi.org/10.1007/s10107-011-0490-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-011-0490-y

Mathematics Subject Classification (2000)

Search

Navigation