Abstract
We obtain new transference bounds that connect two active areas of research: proximity and sparsity of solutions to integer programs. Specifically, we study the additive integrality gap of the integer linear programs \(\min \{{\boldsymbol{c}}\cdot {\boldsymbol{x}}: {\boldsymbol{x}}\in P\cap \mathbb Z^n\}\), where \(P=\{{\boldsymbol{x}}\in \mathbb R^n: \boldsymbol{A}{\boldsymbol{x}}={\boldsymbol{b}}, {\boldsymbol{x}}\ge {\boldsymbol{0}}\}\) is a polyhedron in the standard form determined by an integer \(m\times n\) matrix \(\boldsymbol{A}\) and an integer vector \({\boldsymbol{b}}\). The main result of the paper gives an upper bound for the integrality gap that drops exponentially in the size of support of the optimal solutions corresponding to the vertices of the integer hull of P. Additionally, we obtain a new proximity bound that estimates the \(\ell _2\)-distance from a vertex of P to its nearest integer point in the polyhedron P. The proofs make use of the results from the geometry of numbers and convex geometry.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abdi, A., Cornuéjols, G., Guenin, B., Tunçel, L.: Dyadic linear programming and extensions. arXiv:2309.04601 (2023)
Aliev, I., Averkov, G., De Loera, J.A., Oertel, T.: Sparse representation of vectors in lattices and semigroups. Math. Program. 192, 519–546 (2022)
Aliev, I., Celaya, M., Henk, M., Williams, A.: Distance-sparsity transference for vertices of corner polyhedra. SIAM J. Optim. 31(1), 200–216 (2021)
Aliev, I., De Loera, J.A., Eisenbrand, F., Oertel, T., Weismantel, R.: The support of integer optimal solutions. SIAM J. Optim. 28(3), 2152–2157 (2018)
Aliev, I., De Loera, J.A., Oertel, T., O’Neill, C.: Sparse solutions of linear Diophantine equations. SIAM J. Appl. Algebra Geom. 1(1), 239–253 (2017)
Aliev, I., Henk, M., Oertel, T.: Distances to lattice points in knapsack polyhedra. Math. Program. 182(1–2), 175–198 (2020)
Berndt, S., Jansen, K., Klein, K.-M.: New bounds for the vertices of the integer hull. In: Symposium on Simplicity in Algorithms (SOSA), pp. 25–36. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2021)
Blair, C.E., Jeroslow, R.G.: The value function of a mixed integer program. I. Discrete Math. 19(2), 121–138 (1977)
Blair, C.E., Jeroslow, R.G.: The value function of an integer program. Math. Program. 23(3), 237–273 (1982)
Cassels, J.W.S.: An Introduction to the Geometry of Numbers. Classics in Mathematics. Springer, Heidelberg (1996). https://doi.org/10.1007/978-3-642-62035-5
Celaya, M., Kuhlmann, S., Paat, J., Weismantel, R.: Improving the Cook et al. proximity bound given integral valued constraints. In: Aardal, K., Sanitá, L. (eds.) IPCO 2022. LNCS, vol. 13265, pp. 84–97. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-06901-7_7
Cook, W., Fonlupt, J., Schrijver, A.: An integer analogue of Carathéodory’s theorem. J. Combin. Theory Ser. B 40(1), 63–70 (1986)
Cook, W., Gerards, A.M.H., Schrijver, A., Tardos, É.: Sensitivity theorems in integer linear programming. Math. Program. 34(3), 251–264 (1986)
Dubey, Y., Liu, S.: A short proof of tight bounds on the smallest support size of integer solutions to linear equations. arXiv:2307.08826 (2023)
Eisenbrand, F., Shmonin, G.: Carathéodory bounds for integer cones. Oper. Res. Lett. 34(5), 564–568 (2006)
Eisenbrand, F., Weismantel, R.: 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, pp. 808–816. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2018)
Gomory, R.E.: On the relation between integer and noninteger solutions to linear programs. Proc. Nat. Acad. Sci. U.S.A. 53, 260–265 (1965)
Gomory, R.E.: Some polyhedra related to combinatorial problems. Linear Algebra Appl. 2, 451–558 (1969)
Lee, J., Paat, J., Stallknecht, I., Xu, L.: Improving proximity bounds using sparsity. In: Baïou, M., Gendron, B., Günlük, O., Mahjoub, A.R. (eds.) ISCO 2020. LNCS, vol. 12176, pp. 115–127. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-53262-8_10
Lee, J., Paat, J., Stallknecht, I., Xu, L.: Polynomial upper bounds on the number of differing columns of \(\varDelta \)-modular integer programs. Math. Oper. Res. 48, 2267–2286 (2023)
Oertel, T., Paat, J., Weismantel, R.: The distributions of functions related to parametric integer optimization. SIAM J. Appl. Algebra Geom. 4(3), 422–440 (2020)
Paat, J., Weismantel, R., Weltge, S.: Distances between optimal solutions of mixed-integer programs. Math. Program. 179(1–2), 455–468 (2020)
Sebő, A.: Hilbert bases, Carathéodory’s theorem and combinatorial optimization. In: Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, pp. 431–455. University of Waterloo Press (1990)
Skolem, T.: Diophantische Gleichungen. Ergebnisse der Mathematik, vol 5. Springer, Berlin (1938)
Vaaler, J.D.: A geometric inequality with applications to linear forms. Pacific J. Math. 83(2), 543–553 (1979)
Acknowledgement
The authors thank the anonymous referees for their valuable comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Aliev, I., Celaya, M., Henk, M. (2024). Sparsity and Integrality Gap Transference Bounds for Integer Programs. In: Vygen, J., Byrka, J. (eds) Integer Programming and Combinatorial Optimization. IPCO 2024. Lecture Notes in Computer Science, vol 14679. Springer, Cham. https://doi.org/10.1007/978-3-031-59835-7_1
Download citation
DOI: https://doi.org/10.1007/978-3-031-59835-7_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-59834-0
Online ISBN: 978-3-031-59835-7
eBook Packages: Computer ScienceComputer Science (R0)