Faster Algorithms for Integer Programs with Block Structure

Authors Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.49.pdf
  • Filesize: 465 kB
  • 13 pages

Document Identifiers

Author Details

Friedrich Eisenbrand
  • EPFL, 1015 Lausanne, Switzerland
Christoph Hunkenschröder
  • EPFL, 1015 Lausanne, Switzerland
Kim-Manuel Klein
  • EPFL, 1015 Lausanne, Switzerland

Cite AsGet BibTex

Friedrich Eisenbrand, Christoph Hunkenschröder, and Kim-Manuel Klein. Faster Algorithms for Integer Programs with Block Structure. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 49:1-49:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.49

Abstract

We consider integer programming problems max {c^Tx : A x = b, l <= x <= u, x in Z^{nt}} where A has a (recursive) block-structure generalizing n-fold integer programs which recently received considerable attention in the literature. An n-fold IP is an integer program where A consists of n repetitions of submatrices A in Z^{r × t} on the top horizontal part and n repetitions of a matrix B in Z^{s × t} on the diagonal below the top part. Instead of allowing only two types of block matrices, one for the horizontal line and one for the diagonal, we generalize the n-fold setting to allow for arbitrary matrices in every block. We show that such an integer program can be solved in time n^2t^2 phi x (r s delta)^{O(rs^2+ sr^2)} (ignoring logarithmic factors). Here delta is an upper bound on the largest absolute value of an entry of A and phi is the largest binary encoding length of a coefficient of c. This improves upon the previously best algorithm of Hemmecke, Onn and Romanchuk that runs in time n^3t^3 phi x delta^{O(st(r+t))}. In particular, our algorithm is not exponential in the number t of columns of A and B. Our algorithm is based on a new upper bound on the l_1-norm of an element of the Graver basis of an integer matrix and on a proximity bound between the LP and IP optimal solutions tailored for IPs with block structure. These new bounds rely on the Steinitz Lemma. Furthermore, we extend our techniques to the recently introduced tree-fold IPs, where we again present a more efficient algorithm in a generalized setting.

Subject Classification

ACM Subject Classification
  • Theory of computation → Integer programming
Keywords
  • n-fold
  • Tree-fold
  • Integer Programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Stephan Artmann, Robert Weismantel, and Rico Zenklusen. A strongly polynomial algorithm for bimodular integer linear programming. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1206-1219. ACM, 2017. Google Scholar
  2. Lin Chen and Dániel Marx. Covering a tree with rooted subtrees-parameterized and approximation algorithms. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2801-2820. SIAM, 2018. Google Scholar
  3. Lin Chen, Dániel Marx, Deshi Ye, and Guochuan Zhang. Parameterized and approximation results for scheduling with a low rank processing time matrix. In 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, pages 22:1-22:14, 2017. Google Scholar
  4. William Cook, Jean Fonlupt, and Alexander Schrijver. An integer analogue of caratheodory’s theorem. Journal of Combinatorial Theory, Series B, 40(1):63-70, 1986. Google Scholar
  5. Jesús A De Loera, Raymond Hemmecke, and Matthias Köppe. Algebraic and geometric ideas in the theory of discrete optimization. SIAM, 2012. Google Scholar
  6. Jesús A De Loera, Raymond Hemmecke, Shmuel Onn, and Robert Weismantel. N-fold integer programming. Discrete Optimization, 5(2):231-241, 2008. Google Scholar
  7. Friedrich Eisenbrand and Robert Weismantel. Proximity results and faster algorithms for integer programming using the Steinitz lemma. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 808-816. SIAM, 2018. Google Scholar
  8. Jack E Graver. On the foundations of linear and integer linear programming i. Mathematical Programming, 9(1):207-226, 1975. Google Scholar
  9. Victor S Grinberg and Sergey V Sevast'yanov. Value of the Steinitz constant. Functional Analysis and Its Applications, 14(2):125-126, 1980. Google Scholar
  10. Raymond Hemmecke, Shmuel Onn, and Lyubov Romanchuk. N-fold integer programming in cubic time. Mathematical Programming, pages 1-17, 2013. Google Scholar
  11. Klaus Jansen, Kim-Manuel Klein, Marten Maack, and Malin Rau. Empowering the configuration-ip - new PTAS results for scheduling with setups times. CoRR, abs/1801.06460, 2018. URL: http://arxiv.org/abs/1801.06460.
  12. Ravi Kannan. Minkowski’s convex body theorem and integer programming. Mathematics of Operations Research, 12(3):415-440, 1987. Google Scholar
  13. Dušan Knop and Martin Kouteckỳ. Scheduling meets n-fold integer programming. Journal of Scheduling, pages 1-11, 2017. Google Scholar
  14. Dušan Knop, Martin Koutecký, and Matthias Mnich. Combinatorial n-fold Integer Programming and Applications. In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms (ESA 2017), volume 87 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1-54:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  15. Dušan Knop, Martin Koutecký, and Matthias Mnich. Voting and bribing in single-exponential time. In 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, pages 46:1-46:14, 2017. Google Scholar
  16. Hendrik W Lenstra Jr. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538-548, 1983. Google Scholar
  17. George L Nemhauser and Laurence A Wolsey. Integer and combinatorial optimization. interscience series in discrete mathematics and optimization. ed: John Wiley &Sons, 1988. Google Scholar
  18. Shmuel Onn. Nonlinear discrete optimization. Zurich Lectures in Advanced Mathematics, European Mathematical Society, 2010. Google Scholar
  19. Christos H Papadimitriou. On the complexity of integer programming. Journal of the ACM, 28(4):765-768, 1981. Google Scholar
  20. Alexander Schrijver. Theory of linear and integer programming. John Wiley &Sons, 1998. Google Scholar
  21. Ernst Steinitz. Bedingt konvergente reihen und konvexe systeme. Journal für die reine und angewandte Mathematik, 143:128-176, 1913. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail