Efficient Compilation of Algorithms into Compact Linear Programs

Shermin Khosravi, David Bremner · 2025

Read Efficient Compilation of Algorithms into Compact Linear Programs by Shermin Khosravi, David Bremner (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-13006.txt.

Introduction

Shermin Khosravi and David Bremner shrink the linear programs built from algorithms in 2025. Compilers can turn fast algorithms into programs, but the output is often huge. Huge programs strain solvers in practice.

A layered pipe method splits nested code into synced zones. Each zone holds its own vars and rules. That split cuts size while the program stays valid for all inputs. Tests on span scheduling and lightest tree tasks cut size up to twenty-five fold. Solver speed rose on both paid and free solvers. The path aims at compact forms for hard integer tasks too.

Catalog record

CREATORShermin Khosravi, David Bremner
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-13006

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient Compilation of Algorithms into Compact Linear Programs Shermin Khosravi, David Bremner Abstract While data-driven approaches such as Machine Learning and Artificial Intelligence continue to find new applications across many domains, traditional mathematical optimization frameworks remain highly effective for solving real-world problems having well-defined constraints. In particular, Linear Programming (LP) is widely applied in industry and is a key component of various other mathematical problem-solving techniques. Consequently, LP has attracted significant research interest, particularly in exploring its expressive powers as a computational tool. Recent work introduced an LP compiler translating polynomial-time, polynomial-space algorithms into polynomial-size LPs using intuitive high-level programming languages, offering a promising alternative to manually specifying each set of constraints through Algebraic Modeling Languages (AMLs). However, the resulting LPs, while polynomial in size, are often extremely large, posing challenges for existing LP solvers. In this paper, we propose a novel approach for generating substantially smaller LPs from algorithms. Our goal is to establish minimum-size compact LP formulations for problems in P having natural formulations with exponential extension complexities. Our broader vision is to enable the systematic generation of Compact Integer Programming (CIP) formulations for problems with exponential-size IPs having polynomial-time separation oracles. To this end, we introduce a hierarchical linear pipelining technique that decomposes nested program structures into synchronized regions with well-defined execution transitions—functions of compile-time parameters. This decomposition allows us to localize LP constraints and variables within each region, significantly reducing LP size without the loss of generality, ensuring the resulting LP remains valid for all inputs of size n n . We demonstrate the effectiveness of our method on two benchmark problems—the makespan problem, which has exponential extension complexity, and the weighted minimum spanning tree problem—both of which have exponential-size natural LPs. Our results show up to a 25 25 -fold reduction in LP size and substantial improvements in solver performance across both commercial and non-commercial LP solvers. I Introduction Although data-driven methods, such as Machine Learning and Artificial Intelligence, continue to find new applications, traditional optimization methods remain highly effective for certain real-world problems, particularly when problem-specific constraints are either known or can be extracted from data. For instance, the winning solution of Amazon’s Last Mile Research Challenge, which significantly outperformed alternative solutions, was based on traditional optimization techniques rooted in operations research [ 12 ] . Among these, Linear Programming (LP) is an optimization technique for solving problems defined by linear constraints and objectives. It has a wide range of applications across diverse fields and is at the core of other optimization techniques such as Integer Programming (IP). LP’s pivotal role and widespread applicability have led to the recognition of the simplex algorithm—a well-known LP solving method—as one of the top ten algorithms of the 20 th century [ 16 ] . In particular, an active area of research focuses on determining the minimum LP size required to accurately represent P problems lacking known natural 1 1 1 Formulations based on the problem description, such as a polytope defined by the convex hull of characteristic vectors of a decision problem with a “yes” answer polynomial size LPs. Although polynomial-size LPs have been discovered for some of these problems, there remains interest in finding even smaller LP formulations [ 35 , 18 , 5 , 1 ] ). These efforts not only improve computational efficiency but also achieve tighter relaxations for IP problems and may provide deeper theoretical insights. While exponential-size LPs having polynomial-time separation oracles can be solved in polynomial time using the Ellipsoid method [ 20 ] , the method is rarely used in practice due to its slow convergence. Consequently, finding equivalent but smaller LP formulations eliminates the need for execution of separation algorithms and allows the use of more practical LP algorithms that require a full description of the model [ 10 ] . Unlike with LPs, where larger formulations generally increase solver difficulty [ 29 ] , some large IPs can be solved relatively quickly, while certain small IPs remain unsolved to this day. Nevertheless, since IP solvers mainly rely on repeatedly solving LP relaxations, the model size affects the computational cost of each iteration. This effect is especially pronounced in algorithms that solve the LP relaxation from scratch at every iteration [ 24 ] . In branch-and-cut methods [ 36 ] , runtime increases gradually as additional constraints are generated lazily [ 30 ] . If multiple cuts are added per iteration [ 28 ] , reusing dual information from previous solves can become nearly as costly as solving the LP from scratch. Methods that rely on separation oracles 2 2 2 A black box that, given a point in the solution space, determines whether the point lies within a certain convex set and, if not, returns a hyperplane that separates the point from the set to iteratively narrow down the search often operate on a presolved model. As a result, certain presolving techniques that prevent the translation between presolved and original variables must be disabled to preserve compatibility with the oracle interface [ 21 , 22 ] . Moreover, for certain problems—such as the contact map overlap problem [ 10 ] —the cuts generated by the separation oracle at each iteration yield only small improvements in the objective value, leading to long runtime due to the large number of iterations. Although Algebraic Modeling Languages (AMLs) help with expressing optimization models in a more abstract way, users still have to manually define each set of LP constraints from scratch, which is a tedious task, particularly for more complex models. A recent study [ 7 ] introduces an LP compiler that converts algorithms into LP formulations. When the input algorithm runs in polynomial time and space, the resulting LP is guaranteed to be of polynomial size. This approach allows users to model problems using more intuitive high-level programming languages and enables the construction of polynomial-size LPs for problems in P whose natural polytopes have exponential extension complexity. However, the resulting LPs are often exceptionally large—even for relatively small algorithms—posing challenges for solvers due to memory limitations, numerical stability, and rounding errors. A significant contributor to the LP’s size growth is how the compiler handles the black-box nature of program execution at compile time. To account for all 2^{n} possible execution paths for inputs of size n , the compiler unrolls each line of code across \mathop{\mathrm{TB}}(n) time steps, where \mathop{\mathrm{TB}}(n) is a user-provided upper bound on the number of execution steps. This process generates \mathop{\mathrm{TB}}(n) single-step execution paths per code line, allowing control flow transitions at any time step. Consequently, the model uniformly assumes potential \mathop{\mathrm{TB}}(n) execution frequency for all code lines, even though many of these execution paths may be infeasible or unreachable at runtime. In this paper, we address the black-box nature of execution patterns at compile time by proposing a method inspired by static analysis in abstract interpretation [ 14 ] . Just as abstract interpretation infers reachability using interval abstractions, our approach computes conservative execution time intervals (ETIs), specifying the time ranges during which each code line can be reachable. To enforce these intervals, we draw on the concept of synchronization barriers from multithreaded programming, where execution pauses until all threads reach a designated barrier. Our

Read the complete text