Sparsity and proximity transference in integer programming

• 成果类型: Article; Early Access
• 署名作者: Aliev, Iskander; Celaya, Marcel; Henk, Martin
• 署名单位: Cardiff University; Technical University of Berlin
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02191-z
• 发表日期: 2025

摘要

We obtain new transference bounds that connect the additive integrality gap and sparsity of solutions for integer linear programs. Specifically, we consider the integer programs min{cx:x is an element of P boolean AND Zn}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\min \{{\varvec{c}}\cdot {\varvec{x}}: {\varvec{x}}\in P\cap \mathbb {Z}<^>n\}$$\end{document}, where P={x is an element of Rn:Ax=b,x >= 0}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P=\{{\varvec{x}}\in \mathbb {R}<^>n: \varvec{A}{\varvec{x}}={\varvec{b}}, {\varvec{x}}\ge {\varvec{0}}\}$$\end{document} is a polyhedron in the standard form determined by an integer mxn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m\times n$$\end{document} matrix A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{A}$$\end{document} and an integer vector b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varvec{b}}$$\end{document}. The main result of the paper gives an upper bound for the integrality gap that drops exponentially in the size of the support of the optimal solutions corresponding to the vertices of the integer hull of P. Additionally, we obtain a new proximity estimate for the & ell;2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _2$$\end{document}-distance from a vertex of P to its nearest integer point in P. We also strengthen previously known bounds for the integer Carath & eacute;odory rank, a key sparsity characteristic which estimates the minimum size of the support of an integer point in P in terms of the matrix A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{A}$$\end{document}. The proofs make use of the results from the geometry of numbers and convex geometry.