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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\min \{{\varvec{c}}\cdot {\varvec{x}}: {\varvec{x}}\in P\cap \mathbb {Z}^n\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo movablelimits="true">min</mo> <mo stretchy="false">{</mo> <mrow> <mi mathvariant="bold-italic">c</mi> </mrow> <mo>·</mo> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mo>:</mo> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mo>∈</mo> <mi>P</mi> <mo>∩</mo> <msup> <mrow> <mi mathvariant="double-struck">Z</mi> </mrow> <mi>n</mi> </msup> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$P=\{{\varvec{x}}\in \mathbb {R}^n: \varvec{A}{\varvec{x}}={\varvec{b}}, {\varvec{x}}\ge {\varvec{0}}\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>P</mi> <mo>=</mo> <mo stretchy="false">{</mo> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mo>∈</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>n</mi> </msup> <mo>:</mo> <mrow> <mi mathvariant="bold-italic">A</mi> </mrow> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mo>=</mo> <mrow> <mi mathvariant="bold-italic">b</mi> </mrow> <mo>,</mo> <mrow> <mi mathvariant="bold-italic">x</mi> </mrow> <mo>≥</mo> <mrow> <mn mathvariant="bold">0</mn> </mrow> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> is a polyhedron in the standard form determined by an integer <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$m\times n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>×</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> matrix <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\varvec{A}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">A</mi> </mrow> </math></EquationSource> </InlineEquation> and an integer vector <InlineEquation ID="IEq5"> <EquationSource Format="TEX">${\varvec{b}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">b</mi> </mrow> </math></EquationSource> </InlineEquation>. 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 <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\ell _2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>ℓ</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation>-distance from a vertex of P to its nearest integer point in P. We also strengthen previously known bounds for the integer Carathé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 <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\varvec{A}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">A</mi> </mrow> </math></EquationSource> </InlineEquation>. The proofs make use of the results from the geometry of numbers and convex geometry.

Sparsity and proximity transference in integer programming

期刊论文
出版模式：

开放获取
发表日期：

2025年1月31日

查看全文

Iskander Aliev,
Marcel Celaya,
Martin Henk

摘要

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 \{{\varvec{c}}\cdot {\varvec{x}}: {\varvec{x}}\in P\cap \mathbb {Z}^n\}$ $min {c \cdot x : x \in P \cap Z^{n}}$ , where $P=\{{\varvec{x}}\in \mathbb {R}^n: \varvec{A}{\varvec{x}}={\varvec{b}}, {\varvec{x}}\ge {\varvec{0}}\}$ $P = {x \in R^{n} : A x = b, x \geq 0}$ is a polyhedron in the standard form determined by an integer $m\times n$ $m \times n$ matrix $\varvec{A}$ $A$ and an integer vector ${\varvec{b}}$ $b$ . 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$ $ℓ_{2}$ -distance from a vertex of P to its nearest integer point in P. We also strengthen previously known bounds for the integer Carathé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 $\varvec{A}$ $A$ . The proofs make use of the results from the geometry of numbers and convex geometry.