A parameterized linear formulation of the integer hull
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915562126311424 |
|---|---|
| author | Eisenbrand, Friedrich Rothvoss, Thomas |
| author_facet | Eisenbrand, Friedrich Rothvoss, Thomas |
| contents | Let $A \in \mathbb{Z}^{m \times n}$ be an integer matrix with components bounded by $Δ$ in absolute value. Cook et al.~(1986) have shown that there exists a universal matrix $B \in \mathbb{Z}^{m' \times n}$ with the following property: For each $b \in \mathbb{Z}^m$, there exists $t \in \mathbb{Z}^{m'}$ such that the integer hull of the polyhedron $P = \{ x \in \mathbb{R}^n \colon Ax \leq b\}$ is described by $P_I = \{ x \in \mathbb{R}^n \colon Bx \leq t\}$. Our \emph{main result} is that $t$ is an \emph{affine} function of $b$ as long as $b$ is from a fixed equivalence class of the lattice $D \cdot \mathbb{Z}^m$. Here $D \in \mathbb{N}$ is a number that depends on $n$ and $Δ$ only. Furthermore, $D$ as well as the matrix $B$ can be computed in time depending on $Δ$ and $n$ only. An application of this result is the solution of an open problem posed by Cslovjecsek et al.~(SODA 2024) concerning the complexity of \emph{2-stage-stochastic integer programming} problems. The main tool of our proof is the classical theory of \emph{Chvátal-Gomory cutting planes} and the \emph{elementary closure} of rational polyhedra. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_02347 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A parameterized linear formulation of the integer hull Eisenbrand, Friedrich Rothvoss, Thomas Computational Complexity Optimization and Control Let $A \in \mathbb{Z}^{m \times n}$ be an integer matrix with components bounded by $Δ$ in absolute value. Cook et al.~(1986) have shown that there exists a universal matrix $B \in \mathbb{Z}^{m' \times n}$ with the following property: For each $b \in \mathbb{Z}^m$, there exists $t \in \mathbb{Z}^{m'}$ such that the integer hull of the polyhedron $P = \{ x \in \mathbb{R}^n \colon Ax \leq b\}$ is described by $P_I = \{ x \in \mathbb{R}^n \colon Bx \leq t\}$. Our \emph{main result} is that $t$ is an \emph{affine} function of $b$ as long as $b$ is from a fixed equivalence class of the lattice $D \cdot \mathbb{Z}^m$. Here $D \in \mathbb{N}$ is a number that depends on $n$ and $Δ$ only. Furthermore, $D$ as well as the matrix $B$ can be computed in time depending on $Δ$ and $n$ only. An application of this result is the solution of an open problem posed by Cslovjecsek et al.~(SODA 2024) concerning the complexity of \emph{2-stage-stochastic integer programming} problems. The main tool of our proof is the classical theory of \emph{Chvátal-Gomory cutting planes} and the \emph{elementary closure} of rational polyhedra. |
| title | A parameterized linear formulation of the integer hull |
| topic | Computational Complexity Optimization and Control |
| url | https://arxiv.org/abs/2501.02347 |