Document Open Access Logo

Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming

Authors Marcin Briański, Martin Koutecký, Daniel Král', Kristýna Pekárková, Felix Schröder

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.29.pdf
  • Filesize: 0.65 MB
  • 20 pages

Document Identifiers

Author Details

Marcin Briański
  • Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland
Martin Koutecký
  • Computer Science Institute, Charles University, Prague, Czech Republic
Daniel Král'
  • Faculty of Informatics, Masaryk University, Brno, Czech Republic
Kristýna Pekárková
  • Faculty of Informatics, Masaryk University, Brno, Czech Republic
Felix Schröder
  • Institute of Mathematics, Technische Universität, Berlin, Germany

Funding

The third author was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 648509). This publication reflects only its authors' view; the ERC Executive Agency is not responsible for any use that may be made of the information it contains. The third and fourth authors were supported by the MUNI Award in Science and Humanities (MUNI/I/1677/2018) of the Grant Agency of Masaryk University. The second author was partially supported by Charles University project UNCE/SCI/004 and by the project by the project 19-27871X of GA ČR. First author was partially supported by the Polish National Science Center grant (BEETHOVEN; UMO-2018/31/G/ST1/03718).

Acknowledgements

All five authors would like to thank the Schloss Dagstuhl - Leibniz-Zentrum für Informatik for hospitality during the workshop "Sparsity in Algorithms, Combinatorics and Logic" in September 2021 where the work leading to the results contained in this paper was started.

Cite AsGet BibTex

Marcin Briański, Martin Koutecký, Daniel Král', Kristýna Pekárková, and Felix Schröder. Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.29

Abstract

An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix A and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of A, and when parameterized by the dual tree-depth and the entry complexity of A; both these parameterization imply that A is sparse, in particular, the number of its non-zero entries is linear in the number of columns or rows, respectively. We study preconditioners transforming a given matrix to an equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the 𝓁₁-norm of the Graver basis is bounded by a function of the maximum 𝓁₁-norm of a circuit of A. We use our results to design a parameterized algorithm that constructs a matrix equivalent to an input matrix A that has small primal/dual tree-depth and entry complexity if such an equivalent matrix exists. Our results yield parameterized algorithms for integer programming when parameterized by the 𝓁₁-norm of the Graver basis of the constraint matrix, when parameterized by the 𝓁₁-norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix equivalent to the constraint matrix.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial optimization
  • Mathematics of computing → Matroids and greedoids
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • Integer programming
  • width parameters
  • matroids
  • Graver basis
  • tree-depth
  • fixed parameter tractability

Metrics

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

Related Versions

References

  1. Matthias Aschenbrenner and Raymond Hemmecke. Finiteness theorems in stochastic integer programming. Foundations of Computational Mathematics, 7(2):183-227, 2007. Google Scholar
  2. Cevdet Aykanat, Ali Pinar, and Ümit V. Çatalyürek. Permuting sparse rectangular matrices into block-diagonal form. SIAM Journal on Scientific Computing, 25(6):1860-1879, 2004. Google Scholar
  3. Martin Bergner, Alberto Caprara, Alberto Ceselli, Fabio Furini, Marco E Lübbecke, Enrico Malaguti, and Emiliano Traversi. Automatic Dantzig-Wolfe reformulation of mixed integer programs. Mathematical Programming, 149(1-2):391-424, 2015. Google Scholar
  4. Ralf Borndörfer, Carlos E Ferreira, and Alexander Martin. Decomposing matrices into blocks. SIAM Journal on Optimization, 9(1):236-269, 1998. Google Scholar
  5. Robert Bredereck, Aleksander Figiel, Andrzej Kaczmarczyk, Dušan Knop, and Rolf Niedermeier. High-multiplicity fair allocation made more practical. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, pages 260-268. International Foundation for Autonomous Agents and Multiagent Systems, 2021. Google Scholar
  6. Robert Bredereck, Andrzej Kaczmarczyk, Dušan Knop, and Rolf Niedermeier. High-multiplicity fair allocation: Lenstra empowered by n-fold integer programming. In Proceedings of the 20th ACM Conference on Economics and Computation, pages 505-523. Association for Computing Machinery, 2019. Google Scholar
  7. Timothy F. N. Chan, Jacob W. Cooper, Martin Koutecký, Daniel Král', and Kristýna Pekárková. Matrices of optimal tree-depth and row-invariant parameterized algorithm for integer programming. To appear in SIAM Journal on Computing. Google Scholar
  8. Timothy F. N. Chan, Jacob W. Cooper, Martin Koutecký, Daniel Král', and Kristýna Pekárková. Matrices of optimal tree-depth and row-invariant parameterized algorithm for integer programming. In 47th International Colloquium on Automata, Languages, and Programming (ICALP), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1-26:19, 2020. Google Scholar
  9. Hua Chen, Lin Chen, and Guochuan Zhang. Fpt algorithms for a special block-structured integer program with applications in scheduling. preprint arXiv:2107.01373, 2021. Google Scholar
  10. Lin Chen and Dániel Marx. Covering a tree with rooted subtrees-parameterized and approximation algorithms. In 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2801-2820. SIAM, 2018. Google Scholar
  11. Jana Cslovjecsek, Friedrich Eisenbrand, Christoph Hunkenschröder, Lars Rohwedder, and Robert Weismantel. Block-structured integer and linear programming in strongly polynomial and near linear time. In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1666-1681. SIAM, 2021. Google Scholar
  12. Jana Cslovjecsek, Friedrich Eisenbrand, Michal Pilipczuk, Moritz Venzin, and Robert Weismantel. Efficient sequential and parallel algorithms for multistage stochastic integer programming using proximity. In 29th Annual European Symposium on Algorithms (ESA), volume 204 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1-33:14, 2021. Google Scholar
  13. 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
  14. Matt DeVos, O-joung Kwon, and Sang-il Oum. Branch-depth: Generalizing tree-depth of graphs. European Journal of Combinatorics, 90:103186, 2020. Google Scholar
  15. G. Ding, B. Oporowski, and J. Oxley. On infinite antichains of matroids. Journal of Combinatorial Theory Series B, 63(1):21-40, 1995. Google Scholar
  16. 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), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1-49:13, 2018. Google Scholar
  17. Farbod Ekbatani, Bento Natura, and László A. Végh. Circuit imbalance measures and linear programming. preprint arXiv:2108.03616, 2021. Google Scholar
  18. Michael C. Ferris and Jeffrey D. Horn. Partitioning mathematical programs for parallel solution. Mathematical Programming, 80(1):35-61, 1998. Google Scholar
  19. Gerald Gamrath and Marco E. Lübbecke. Experiments with a generic Dantzig-Wolfe decomposition for integer programs. Experimental Algorithms, 6049:239-252, 2010. Google Scholar
  20. Robert Ganian and Sebastian Ordyniak. The complexity landscape of decompositional parameters for ILP. Artificial Intelligence, 257:61-71, 2018. Google Scholar
  21. P.R. Halmos. Finite-Dimensional Vector Spaces. Undergraduate Texts in Mathematics. Springer, 1993. Google Scholar
  22. Raymond Hemmecke, Shmuel Onn, and Lyubov Romanchuk. N-fold integer programming in cubic time. Mathematical Programming, 137:325-341, 2013. Google Scholar
  23. Raymond Hemmecke and Rüdiger Schultz. Decomposition of test sets in stochastic integer programming. Mathematical Programming, 94:323-341, 2003. Google Scholar
  24. Danny Hermelin, Hendrik Molter, Rolf Niedermeier, and Dvir Shabtay. Equitable scheduling for the total completion time objective. preprint arXiv:2112.13824, 2021. Google Scholar
  25. Petr Hliněný. Branch-width, parse trees, and monadic second-order logic for matroids. In 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 2607 of LNCS, pages 319-330, 2003. Google Scholar
  26. Petr Hliněný. Branch-width, parse trees, and monadic second-order logic for matroids. Journal of Combinatorial Theory Series B, 96(3):325-351, 2006. Google Scholar
  27. Klaus Jansen, Kim-Manuel Klein, and Alexandra Lassota. The double exponential runtime is tight for 2-stage stochastic ILPs. In Integer Programming and Combinatorial Optimization - 22nd International Conference (IPCO), volume 12707 of Lecture Notes in Computer Science, pages 297-310. Springer, 2021. Google Scholar
  28. Klaus Jansen, Kim-Manuel Klein, Marten Maack, and Malin Rau. Empowering the configuration-ip: new ptas results for scheduling with setup times. To appear in Mathematical Programming. Google Scholar
  29. Klaus Jansen, Kim-Manuel Klein, Marten Maack, and Malin Rau. Empowering the configuration-IP - new PTAS results for scheduling with setups times. preprint arXiv:1801.06460, 2018. Google Scholar
  30. Klaus Jansen, Alexandra Lassota, and Marten Maack. Approximation algorithms for scheduling with class constraints. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pages 349-357. Association for Computing Machinery, 2020. Google Scholar
  31. Klaus Jansen, Alexandra Lassota, and Lars Rohwedder. Near-linear time algorithm for n-fold ILPs via color coding. SIAM Journal on Discrete Mathematics, 34(4):2282-2299, 2020. Google Scholar
  32. Ravi Kannan. Minkowski’s convex body theorem and integer programming. Mathematics of Operations Research, 12(3):415-440, August 1987. Google Scholar
  33. František Kardoš, Daniel Král', Anita Liebenau, and Lukáš Mach. First order convergence of matroids. European Journal of Combinatorics, 59:150-168, 2017. Google Scholar
  34. Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, The IBM Research Symposia Series, pages 85-103. Springer, 1972. Google Scholar
  35. Taghi Khaniyev, Samir Elhedhli, and Fatih Safa Erenay. Structure detection in mixed-integer programs. INFORMS Journal on Computing, 30(3):570-587, 2018. Google Scholar
  36. Kim-Manuel Klein. About the complexity of two-stage stochastic IPs. To appear in Mathematical Programming. Google Scholar
  37. Kim-Manuel Klein and Janina Reuter. Collapsing the tower - on the complexity of multistage stochastic ips. In 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 348-358. SIAM, 2022. Google Scholar
  38. Dušan Knop and Martin Koutecký. Scheduling kernels via configuration LP. preprint arXiv:2003.02187, 2018. Google Scholar
  39. Dušan Knop and Martin Koutecký. Scheduling meets n-fold integer programming. Journal of Scheduling, 21(5):493-503, 2018. Google Scholar
  40. Martin Koutecký, Asaf Levin, and Shmuel Onn. A parameterized strongly polynomial algorithm for block structured integer programs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP), volume 107, pages 85:1-85:14, 2018. Google Scholar
  41. Hendrik W. Lenstra, Jr. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538-548, 1983. Google Scholar
  42. James Oxley. Matroid Theory. Oxford Graduate Texts in Mathematics. Oxford University Press, 2011. Google Scholar
  43. Alex Pothen. The complexity of optimal elimination trees. Technical Report CS-88-13, Pennsylvania State University, 1988. Google Scholar
  44. Rüdiger Schultz, Leen Stougie, and Maarten H. van der Vlerk. Solving stochastic programs with integer recourse by enumeration: A framework using gröbner basis reductions. Mathematical Programming, 83:229-252, 1998. Google Scholar
  45. François Vanderbeck and Laurence A Wolsey. Reformulation and decomposition of integer programs. In 50 Years of Integer Programming 1958-2008, pages 431-502. Springer, 2010. Google Scholar
  46. Jiadong Wang and Ted Ralphs. Computational experience with hypergraph-based methods for automatic decomposition in discrete optimization. In Proceedings of the 10th International Conference on Integration of Constraint Programming, pages 394-402. Springer, 2013. Google Scholar
  47. Roman L. Weil and Paul C. Kettler. Rearranging matrices to block-angular form for decomposition (and other) algorithms. Management Science, 18(1):98-108, 1971. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact