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 a row-equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse row-equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the ℓ 1 -norm of the Graver basis is bounded by a function of the maximum ℓ 1 -norm of a circuit of A. We use our results to design a parameterized algorithm that constructs a matrix row-equivalent to an input matrix A that has small primal/dual tree-depth and entry complexity if such a row-equivalent matrix exists. Our results yield parameterized algorithms for integer programming when parameterized by the ℓ 1 -norm of the Graver basis of the constraint matrix, when parameterized by the ℓ 1 -norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix.

Computer Science Institute Charles University Prague Czech Republic

Faculty of Informatics Masaryk University Brno Czech Republic

Faculty of Mathematics and Physics Charles University Prague Czech Republic

Theoretical Computer Science Department Faculty of Mathematics and Computer Science Jagiellonian University Kraków Poland

Zobrazit více v PubMed

Aschenbrenner, M., Hemmecke, R.: Finiteness theorems in stochastic integer programming. Found. Comput. Math. 7(2), 183–227 (2007)

Aykanat, C., Pinar, A., Çatalyürek, Ü.V.: Permuting sparse rectangular matrices into block-diagonal form. SIAM J. Sci. Comput. 25(6), 1860–1879 (2004)

Bergner, M., Caprara, A., Ceselli, A., Furini, F., Lübbecke, M.E., Malaguti, E., Traversi, E.: Automatic Dantzig–Wolfe reformulation of mixed integer programs. Math. Program. 149(1–2), 391–424 (2015)

Borndörfer, R., Ferreira, C.E., Martin, A.: Decomposing matrices into blocks. SIAM J. Optim. 9(1), 236–269 (1998)

Brand, C., Koutecký, M., Ordyniak, S.: Parameterized algorithms for MILPs with small treedepth. Proc. AAAI Conf. Artif. Intell. 35(14), 12249–12257 (2021)

Bredereck, R., Figiel, A., Kaczmarczyk, A., Knop, D., Niedermeier, R.: High-multiplicity fair allocation made more practical. In: Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS’21, pp. 260–268. International Foundation for Autonomous Agents and Multiagent Systems (2021)

Bredereck, R., Kaczmarczyk, A., Knop, D., Niedermeier, R.: High-multiplicity fair allocation: Lenstra empowered by n-fold integer programming. In: Proceedings of the 2019 ACM Conference on Economics and Computation, EC’19, pp. 505–523. Association for Computing Machinery (2019)

Chan, T.F.N., Cooper, J.W., Koutecký, M., Král’, D., Pekárková, K.: Matrices of optimal tree-depth and row-invariant parameterized algorithm for integer programming. In: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 168, pp. 26:1–26:19 (2020)

Chan, T.F.N., Cooper, J.W., Koutecký, M., Král’, D., Pekárková, K.: Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming. SIAM J. Comput. 51(3), 664–700 (2022)

Chen, H., Chen, L., Zhang, G.: FPT algorithms for a special block-structured integer program with applications in scheduling. preprint arXiv:2107.01373 (2021)

Chen, L., Marx, D.: Covering a tree with rooted subtrees–parameterized and approximation algorithms. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 2801–2820. SIAM (2018)

Cslovjecsek, J., Eisenbrand, F., Hunkenschröder, C., Rohwedder, L., Weismantel, R.: Block-structured integer and linear programming in strongly polynomial and near linear time. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pp. 1666–1681. SIAM (2021)

Cslovjecsek, J., Eisenbrand, F., Pilipczuk, M., Venzin, M., Weismantel, R.: Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity. In: 29th Annual European Symposium on Algorithms (ESA 2021), Leibniz International Proceedings in Informatics (LIPIcs), vol. 204, pp. 33:1–33:14 (2021)

Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)

De Loera, J.A., Hemmecke, R., Onn, S., Weismantel, R.: [Image: see text]-fold integer programming. Discret. Optim. 5(2), 231–241 (2008)

DeVos, M., Kwon, O., Oum, S.: Branch-depth: Generalizing tree-depth of graphs. Eur. J. Comb. 90, 103186 (2020)

Ding, G., Oporowski, B., Oxley, J.: On infinite antichains of matroids. J. Comb. Theory Ser. B 63(1), 21–40 (1995)

Eiben, E., Ganian, R., Knop, D., Ordyniak, S., Pilipczuk, M., Wrochna, M.: Integer programming and incidence tree depth. In: Integer Programming and Combinatorial Optimization—20th International Conference (IPCO), LNCS vol. 11480, pp. 194–204. Springer International Publishing (2019)

Eisenbrand, F., Hunkenschröder, C., Klein, K.: 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), pp. 49:1–49:13 (2018)

Eisenbrand, F., Hunkenschröder, C., Klein, K., Koutecký, M., Levin, A., Onn, S.: An algorithmic theory of integer programming. preprint arXiv:1904.01361 (2019)

Ekbatani, F., Natura, B., Végh, L.A.: Circuit imbalance measures and linear programming. preprint arXiv:2108.03616 (2021)

Ferris, M.C., Horn, J.D.: Partitioning mathematical programs for parallel solution. Math. Program. 80(1), 35–61 (1998)

Gamrath, G., Lübbecke, M.E.: Experiments with a generic Dantzig–Wolfe decomposition for integer programs. Exp. Algorithms 6049, 239–252 (2010)

Ganian, R., Ordyniak, S.: The complexity landscape of decompositional parameters for ILP. Artif. Intell. 257, 61–71 (2018)

Halmos, P.: Finite-Dimensional Vector Spaces. Undergraduate Texts in Mathematics, Springer, Berlin (1993)

Hemmecke, R., Onn, S., Romanchuk, L.: [Image: see text]-fold integer programming in cubic time. Math. Program. 137, 325–341 (2013)

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

Hermelin, D., Molter, H., Niedermeier, R., Shabtay, D.: Equitable scheduling for the total completion time objective. preprint arXiv:2112.13824 (2021)

Hliněný, P.: Branch-width, parse trees, and monadic second-order logic for matroids. In: H. Alt, M. Habib (eds.) 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS), LNCS, vol. 2607, pp. 319–330 (2003)

Hliněný, P.: Branch-width, parse trees, and monadic second-order logic for matroids. J. Comb. Theory Ser. B 96(3), 325–351 (2006)

Jansen, K., Klein, K., Lassota, A.: The double exponential runtime is tight for 2-stage stochastic ILPs. In: M. Singh, D.P. Williamson (eds.) Integer Programming and Combinatorial Optimization—22nd International Conference (IPCO), LNCS vol. 12707, Lecture Notes in Computer Science, vol. 12707, pp. 297–310. Springer (2021)

Jansen, K., Klein, K., Maack, M., Rau, M.: Empowering the configuration-IP: new PTAS results for scheduling with setup times. Math. Program. (2021)

Jansen, K., Lassota, A., Maack, M.: Approximation algorithms for scheduling with class constraints. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 349–357. Association for Computing Machinery (2020)

Jansen, K., Lassota, A., Rohwedder, L.: Near-linear time algorithm for [Image: see text]-fold ILPs via color coding. SIAM J. Discret. Math. 34(4), 2282–2299 (2020)

Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415–440 (1987)

Kardoš, F., Král’, D., Liebenau, A., Mach, L.: First order convergence of matroids. Eur. J. Comb. 59, 150–168 (2017)

Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85–103. Springer, Berlin (1972)

Khaniyev, T., Elhedhli, S., Erenay, F.S.: Structure detection in mixed-integer programs. INFORMS J. Comput. 30(3), 570–587 (2018)

Klein, K.: About the complexity of two-stage stochastic IPs. Math. Program. 192(1), 319–337 (2022) PubMed PMC

Klein, K., Reuter, J.: Collapsing the tower—on the complexity of multistage stochastic IPs. In: 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pp. 348–358. SIAM (2022)

Knop, D., Koutecký, M.: Scheduling kernels via configuration LP. preprint arXiv:2003.02187 (2018)

Knop, D., Koutecký, M.: Scheduling meets [Image: see text]-fold integer programming. J. Sched. 21(5), 493–503 (2018)

Knop, D., Koutecký, M., Mnich, M.: Combinatorial n-fold integer programming and applications. In: 25th Annual European Symposium on Algorithms (ESA), Leibniz International Proceedings in Informatics (LIPIcs), vol. 87, pp. 54:1–54:14 (2017)

Koutecký, M., Levin, A., Onn, S.: A parameterized strongly polynomial algorithm for block structured integer programs. In: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 107, pp. 85:1–85:14 (2018)

Lenstra, H.W., Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538–548 (1983)

Oxley, J.: Matroid Theory. Oxford Graduate Texts in Mathematics, Oxford University Press, Oxford (2011)

Pothen, A.: The complexity of optimal elimination trees. Technical Report CS-88-13, Pennsylvania State University (1988)

Schultz, R., Stougie, L., van der Vlerk, M.H.: Solving stochastic programs with integer recourse by enumeration: a framework using gröbner basis reductions. Math. Program. 83, 229–252 (1998)

Vanderbeck, F., Wolsey, L.A.: Reformulation and decomposition of integer programs. In: 50 Years of Integer Programming 1958–2008, pp. 431–502. Springer (2010)

Wang, J., Ralphs, T.: Computational experience with hypergraph-based methods for automatic decomposition in discrete optimization. In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pp. 394–402. Springer (2013)

Weil, R.L., Kettler, P.C.: Rearranging matrices to block-angular form for decomposition (and other) algorithms. Manag. Sci. 18(1), 98–108 (1971)