Paperlane

no. 16 · Tuesday 17 November 2026

Solving Linear and Integer Programs Faster Using Data

Yuhan Ye and Omar Bennouna

math.OC · v3 · 32 pp

Abstract

We study how much a linear program (LP) or an integer program (IP) can be compressed when solved repeatedly over a fixed feasible region with varying objective coefficients. We provide a framework that compresses LP and IP formulations with guarantees on the probability of preserving optimality, using either an uncertainty set for the cost vector or historical samples. Our framework exposes a tunable tradeoff between compression and the probability of recovering an optimal solution. We characterize the minimum dimension of affine reformulations preserving the full optimizer set over a given cost region and provide sample-based learning algorithms with fast-rate guarantees, without requiring a nondegeneracy assumption for LPs. With high confidence over the training data, the learned reformulation preserves the optimizer set for an independent test cost with probability at least $1-ρ-\widetilde{O}(d^\star_ρ/n)$, where $ρ$ bounds the excluded probability mass and $d^\star_ρ$ is the retained region's decision-relevant dimension. Existing data-driven approaches to LP and IP reduction do not, to our knowledge, learn a single low-dimensional affine reformulation with a prescribed probability of preserving the full optimizer set. Experimental results show substantial improvements over the compared baselines in accuracy, sample efficiency, and computational speed.

comments
Accepted at NeurIPS 2026. 32 pages, 11 figures
fields
Optimization and Control
pdf ↗ page arXiv:2605.25635 ↗