Sparsity and proximity transference in integer programming

Aliev, Iskander ORCID: https://orcid.org/0000-0002-2206-9207, Celaya, Marcel ORCID: https://orcid.org/0000-0003-3480-4835 and Henk, Martin 2025. Sparsity and proximity transference in integer programming. Mathematical Programming 10.1007/s10107-024-02191-z

Preview

PDF - Published Version Available under License Creative Commons Attribution. Download (370kB) | Preview

Abstract

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 in P, x integer}, where P={x: Ax=b, x nonnegative} is a polyhedron in the standard form determined by an integer mxn matrix A and an integer vector 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 distance from a vertex of P to its nearest integer point in P. We also strengthen previously known bounds for the integer Caratheodory 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. The proofs make use of the results from the geometry of numbers and convex geometry.

Item Type:	Article
Date Type:	Published Online
Status:	In Press
Schools:	Schools > Mathematics
Publisher:	Springer
ISSN:	0025-5610
Funders:	EPSRC
Date of First Compliant Deposit:	23 December 2024
Date of Acceptance:	23 December 2024
Last Modified:	06 Mar 2025 14:28
URI:	https://orca.cardiff.ac.uk/id/eprint/174907

Actions (repository staff only)

Edit Item