Efficient Conversion of Algorithms to Linear Programs

Abstract

The expressiveness of Linear Programming (LP) has motivated research on an LP compiler that generates polynomial-size LPs for polynomial-time solvable problems, including those having exponential extension complexity. By automating modeling from high-level algorithmic descriptions, the compiler offers a promising alternative to algebraic modelling languages. However, the resulting LPs are extremely large, posing challenges for existing solvers. Recently, we have introduced two LP compiler optimizations, namely Hierarachical Synchronization Barriers (HSB) and Constraint Sharing (CS), that address this challenge by exploiting structural and similarity-based patterns derived from the source code and the design of compiler-generated LPs, beyond what conventional compiler and presolve techniques can achieve in isolation. In this paper, we provide a comprehensive evaluation of these optimization methods on fundamental combinatorial algorithms and introduce the Execution Domain Aware (EDA) optimization framework to address a limitation revealed by this analysis. The framework reinterprets structural synchronizations as a time abstraction layer within which other optimizations can target localized reductions while remaining agnostic to time-step transitions. Across a broad suite of benchmarks, HSB and CS consistently generate smaller LPs, achieving LP file-size reductions of up to 96% and 53%, respectively, while also improving numerical conditioning, solver performance, and solution quality. HSB provides the strongest and most robust overall gains. The EDA framework further broadens the range of benchmarks that can benefit from HSB when its underlying structural assumptions are less effective. We view this work as a step toward systematic generation of Compact Integer Programming formulations for problems with exponential-size Integer Programs having polynomial-time separation oracles.

Continuous-time analysis and algorithms for linear and convex quadratic programs via exactly solvable differential inclusions
Gabriel P. Langlois, Akwum Onwunta, Jérôme Darbon
arXiv21 Oct 2026PreprintCC BY 4.0Full textDynamical systems Optimisation & controlarXiv
Efficient ADMM for Soft-Constrained Quadratic Programs via Generalized Slack Projections
Roland Schwan, Thomas Lew, Brian Plancher
arXiv26 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Efficient Algorithms for Energy-Aware Single-Machine Scheduling with Battery Storage
Luca Forte, Stijn De Vuyst, Pieter Leyman
arXiv10 Sep 2026PreprintCC BY-NC-SA 4.0Full textOptimisation & controlarXiv
Sparse Dictionary Learning for Measure-Valued Data via Linearized Optimal Transport: Efficient Algorithms and Sample Complexity
Brendan Mallery, Shuchin Aeron, James Murphy
arXiv9 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
Feasibility Correction in Linear Programs
Pedro Abdalla, Roman Vershynin, Guangyi Zou
arXiv28 Sep 2026PreprintarXiv licenceFull textOptimisation & control ProbabilityarXiv

Cite

BibTeX RIS

BibTeX

@misc{khosravi2026efficient,
  title = {{Efficient Conversion of Algorithms to Linear Programs}},
  author = {Shermin Khosravi and David Bremner},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.12896},
  eprint = {2611.12896},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.12896},
  note = {CC BY-NC-ND 4.0},
}

RIS

TY  - UNPB
TI  - Efficient Conversion of Algorithms to Linear Programs
AU  - Shermin Khosravi
AU  - David Bremner
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.12896
UR  - https://arxiv.org/abs/2611.12896
AB  - The expressiveness of Linear Programming (LP) has motivated research on an LP compiler that generates polynomial-size LPs for polynomial-time solvable problems, including those having exponential extension complexity. By automating modeling from high-level algorithmic descriptions, the compiler offers a promising alternative to algebraic modelling languages. However, the resulting LPs are extremely large, posing challenges for existing solvers. Recently, we have introduced two LP compiler optimizations, namely Hierarachical Synchronization Barriers (HSB) and Constraint Sharing (CS), that address this challenge by exploiting structural and similarity-based patterns derived from the source code and the design of compiler-generated LPs, beyond what conventional compiler and presolve techniques can achieve in isolation. In this paper, we provide a comprehensive evaluation of these optimization methods on fundamental combinatorial algorithms and introduce the Execution Domain Aware (EDA) optimization framework to address a limitation revealed by this analysis. The framework reinterprets structural synchronizations as a time abstraction layer within which other optimizations can target localized reductions while remaining agnostic to time-step transitions. Across a broad suite of benchmarks, HSB and CS consistently generate smaller LPs, achieving LP file-size reductions of up to 96% and 53%, respectively, while also improving numerical conditioning, solver performance, and solution quality. HSB provides the strongest and most robust overall gains. The EDA framework further broadens the range of benchmarks that can benefit from HSB when its underlying structural assumptions are less effective. We view this work as a step toward systematic generation of Compact Integer Programming formulations for problems with exponential-size Integer Programs having polynomial-time separation oracles.
ER  -

Abstract

Related

Cite