Efficient Compilation of Algorithms into Compact Linear Programs
Preprint
Abstract
Linear Programming (LP) is widely applied in industry and is a key component of various other mathematical problem-solving techniques. 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$. 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$-fold reduction in LP size and substantial improvements in solver performance across both commercial and non-commercial LP solvers.
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- A survey for solving mixed integer programming via machine learningNeurocomputing, 2022
- Polynomial size linear programs for problems in PDiscrete Applied Mathematics, 2019
- Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-Genus GraphsDiscrete & Computational Geometry, 2017
- Deriving compact extended formulations via LP-based separation techniquesAnnals of Operations Research, 2015
- Widening and narrowing operators for abstract interpretationComputer Languages, Systems & Structures, 2011
- Compact vs. exponential-size LP relaxationsOperations Research Letters, 2002
- A linear‐size zero—one programming model for the minimum spanning tree problem in planar graphsNetworks, 2001
- Using separation algorithms to generate mixed integer model reformulationsOperations Research Letters, 1991
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981
- Linear programming is log-space hard for PInformation Processing Letters, 1979