Papers for

integer programming solvers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Quadratic bound established for complexity of 0 1 polytope cutting processes

A quadratic upper bound on the Chvátal rank of polytopes in the 0/1-cube

Abstract: We show that every polytope $P\subseteq[0,1]^n$, and more generally every compact convex set, has Chvátal rank at most $12.22n^2+n\log_2 n+2n+4$. This improves the $O(n^2\log n)$ bound of Eisenbrand and Schulz and, together with the $Ω(n^2)$ lower bound of Rothvoß and Sanità, shows that the maximum Chvátal rank of a polytope in $[0,1]^n$ is $Θ(n^2)$. More precisely, if $P$ contains an integer point, then for every $c\in\mathbb{Z}^n\setminus\{0\}$ the inequality $cx\le\max\{cy: y\in P\cap\mathbb{Z}^n\}$ is valid for the $k$-th Chvátal closure of $P$ for some $k\le 12.22n^2+2n+2\log_2\|c\|_\infty+4$. Following Eisenbrand and Schulz, we derive this inequality along a chain of coarser and coarser integer vectors, but instead of halving the vector in each step, we round $τc$ for a scale $τ$ chosen freely in each dyadic window $[2^{-t-1},2^{-t}]$. The main new ingredient is a multiscale version of Dirichlet's approximation theorem, proved by an elementary volume argument: for every $c\in\mathbb{R}^n$, the $\ell_1$-distances of $τc$ to $\mathbb{Z}^n$, minimized within each dyadic window and summed over all windows, total less than $1.222n^2$, independently of $\|c\|_\infty$.

Sat 26 SeptDiscrete Mathematics
The gist
The paper focuses on how complex it is to simplify shapes called polytopes made from 0s and 1s using a process known as Chvátal closures. The authors prove that the number of steps needed follows a pattern that grows like the square of the dimension size, improving previous estimates. They introduce a new mathematical technique to manage these steps more efficiently, based on approximating numbers at multiple scales. Their result confirms that the complexity scales quadratically with dimension and narrows down the exact growth rate.
Open → 2609.32210v1