Reproduce “FLARE: Verifying MILP Reformulations with LLM-Based Theorem Proving” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Henry Robbins, Connor Lawless, Madeleine Udell, Ellen Vitercik
FLARE uses an LLM-based agent to formalize mixed-integer linear programming (MILP) reformulations in Lean and generate proofs that a transformation preserves feasibility and objective relationships across all instances covered by the formalization. On a benchmark of 54 reformulation pairs, it classified all pairs correctly and produced machine-checkable certificates; a faster natural-language variant also achieved perfect accuracy but provides no formal guarantee.
Key insights
- A proof over formally represented formulations can check a transformation across all represented instances, unlike tests that compare outcomes on selected inputs.
- The constructive definition checks relationships across feasible solutions, not only whether optimal values happen to match.
- Verification depends on faithful formalization: Lean certifies the encoded claim, while omissions or errors in translating the original model and assumptions can limit what the certificate establishes.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.