Overview
Integer programming (IP) is a core methodology for combinatorial optimization, but solving IP problems is constrained by their NP-hard computational complexity. A common operational strategy to improve IP solver performance involves designing inequality families that exploit the structural characteristics of a given problem. However, this process has historically relied on manual design by human experts. The Symbolic Acceleration via Generative Evolution (SAGE) framework automates the discovery of these acceleration inequality families at the modeling level.
Research Context
While introducing specialized inequality families can substantially enhance solver efficiency, manual derivation demands deep mathematical expertise and problem-specific intuition. Consequently, automating the creation of reusable, structural inequality families has presented a persistent difficulty in mathematical programming and combinatorial optimization research.
Approach
SAGE identifies acceleration inequality families by jointly processing a symbolic IP formulation and a natural language description of the problem. Rather than constructing inequalities on an instance-by-instance basis or relying on rigorous mathematical proofs, the system discovers symbolic formulations that are instantiated for individual problem instances and validated through empirical admissibility and impact screening.
The framework executes in three distinct stages:
- Population Initialization: An initializer agent utilizing a large language model (LLM) generates an initial population of candidate acceleration inequality families.
- Empirical Admissibility Screening: Candidate inequalities are tested on a small development admissibility set to verify solution feasibility and confirm the separation of the relaxation solution.
- Evolutionary Refinement: The population of candidate inequalities is iteratively improved through evolutionary crossover and mutation agents.
Findings
Evaluation across seven mixed-integer linear programming (MILP) benchmarks yielded the following results:
- Optimality Gap Reductions: When executed under fixed time budgets, SAGE reduced optimality gaps by up to $62.1\%$ relative to baseline MILP formulations.
- Runtime Speedups: Measured by shifted geometric mean speedup, the framework attained target optimality gaps up to $5.51\times$ faster than standard baselines.
- Ablation and Transfer Robustness: Ablation experiments demonstrated that performance improvements remained consistent across different LLM backends, varied mathematical solvers, and diverse internal cut parameter settings.