The Geometry of Linear Program Compression: An Exact Characterization and Learning Algorithm
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914599359479808 |
|---|---|
| author | Ye, Yuhan Bennouna, Omar |
| author_facet | Ye, Yuhan Bennouna, Omar |
| contents | We study how much a linear program (LP) can be compressed when solved repeatedly, given prior knowledge about its objective function. Existing data-driven projection methods learn low-dimensional surrogate LPs with approximate objective-value guarantees, but cannot provably identify the optimal projection for a prescribed compression budget. We instead ask a sharper question: how far can an LP be compressed into a lower-dimensional equivalent while \emph{exactly} preserving optimality, enabling faster repeated solves with no loss in solution quality? We provide an exact geometric characterization of such compressed LPs, together with a tractable sample-based learning algorithm that comes with fast-rate guarantees: the compressed LP recovers the optimal solution of an unseen instance with probability at least $1-\widetilde O(d^\star/n)$, where $d^\star$ is the dimension of the decision-relevant subspace, and $n$ is the number of available historical LP samples. This $1/n$ dependence is sharper than the $\widetilde O(1/\sqrt n)$ uniform-convergence rates of approximate projection methods. Our framework further exposes a tunable tradeoff between the dimension of the compressed LP and the probability of recovering the optimal solution, allowing the user to trade compression for accuracy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_25635 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Geometry of Linear Program Compression: An Exact Characterization and Learning Algorithm Ye, Yuhan Bennouna, Omar Optimization and Control 90C05 (Primary), 90C60, 68Q32, 90C31, 52B55 (Secondary) We study how much a linear program (LP) can be compressed when solved repeatedly, given prior knowledge about its objective function. Existing data-driven projection methods learn low-dimensional surrogate LPs with approximate objective-value guarantees, but cannot provably identify the optimal projection for a prescribed compression budget. We instead ask a sharper question: how far can an LP be compressed into a lower-dimensional equivalent while \emph{exactly} preserving optimality, enabling faster repeated solves with no loss in solution quality? We provide an exact geometric characterization of such compressed LPs, together with a tractable sample-based learning algorithm that comes with fast-rate guarantees: the compressed LP recovers the optimal solution of an unseen instance with probability at least $1-\widetilde O(d^\star/n)$, where $d^\star$ is the dimension of the decision-relevant subspace, and $n$ is the number of available historical LP samples. This $1/n$ dependence is sharper than the $\widetilde O(1/\sqrt n)$ uniform-convergence rates of approximate projection methods. Our framework further exposes a tunable tradeoff between the dimension of the compressed LP and the probability of recovering the optimal solution, allowing the user to trade compression for accuracy. |
| title | The Geometry of Linear Program Compression: An Exact Characterization and Learning Algorithm |
| topic | Optimization and Control 90C05 (Primary), 90C60, 68Q32, 90C31, 52B55 (Secondary) |
| url | https://arxiv.org/abs/2605.25635 |