Agentic Dual Verification and Dual Reduction Discovery for Mathematical Optimization
This project develops AI agents that automatically discover dual reductions and verification strategies for mathematical optimization problems. By treating dual problem construction as a search over reformulation spaces, the agents learn to identify hidden structure (e.g., constraint aggregation, variable substitutions, Lagrangian decompositions) that tighten relaxations and accelerate solvers, while simultaneously certifying optimality bounds through learned verifiers.
🧑‍🎓 IOL Project Members
🪙 Funding
This project is being funded by the Berlin Mathematics Research Center MATH+ (project ID EF-LI-Opt-6), itself funded by the German Research Foundation (DFG) under Germany's Excellence Strategy (EXC-2046/1, project ID 390685689) from October 2026 to September 2029.
🔬 Project Description
A central tension in mathematical optimization is that tighter problem formulations lead to faster solve times, but constructing tight formulations is itself a hard problem requiring deep domain expertise. Dual reductions—such as variable aggregation, constraint elimination, and Lagrangian decomposition—can dramatically tighten formulations, but they are typically discovered manually or through static, rule-based pre-processing.
This project proposes a fundamentally different approach: agentic AI systems that learn to navigate the space of dual reformulations, discovering reduction strategies that are:
- Problem-specific rather than one-size-fits-all;
- Verified through learned dual certificates that provide rigorous optimality guarantees;
- Transferable across related problem classes through meta-learning.
The project combines techniques from reinforcement learning (for exploring the reformulation space), learned verification (for certifying dual bounds), and large language models (for interpreting problem structure and generating human-readable reduction proofs).