# EquivaMap: Leveraging LLMs for Automatic Equivalence Checking of Optimization Formulations

arXiv: https://arxiv.org/abs/2502.14760 · HTML: https://mlsanity.com/paper/2502.14760/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 39 references that are in the map.
- First posted on arXiv 20 Feb 2025.

## Builds on (most cited first, 18 of 18)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [NL4Opt Competition: Formulating Optimization Problems Based on Their Natural Language Descriptions](https://mlsanity.com/paper/2303.08233/) (2023)
- [OptiMUS: Scalable Optimization Modeling with (MI)LP Solvers and Large Language Models](https://mlsanity.com/paper/2402.10172/) (2024)
- [OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling](https://mlsanity.com/paper/2407.09887/) (2024)
- [Large Language Models for Supply Chain Optimization](https://mlsanity.com/paper/2307.03875/) (2023)
- [Autoformulation of Mathematical Optimization Models Using LLMs](https://mlsanity.com/paper/2411.01679/) (2024)
- [On Representing Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2209.12288/) (2022)
- [Diagnosing Infeasible Optimization Problems Using Large Language Models](https://mlsanity.com/paper/2308.12923/) (2023)
- [On Representing Mixed-Integer Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2210.10759/) (2022)
- [When Large Language Model Meets Optimization](https://mlsanity.com/paper/2405.10098/) (2024)
- ["I Want It That Way": Enabling Interactive Decision Support Using Large Language Models and Constraint Programming](https://mlsanity.com/paper/2312.06908/) (2023)
- [Synthesizing mixed-integer linear programming models from natural language descriptions](https://mlsanity.com/paper/2311.15271/) (2023)
- [LM4OPT: Unveiling the Potential of Large Language Models in Formulating Mathematical Optimization Problems](https://mlsanity.com/paper/2403.01342/) (2024)
- [Deep Insights into Automated Optimization with Large Language Models and Evolutionary Algorithms](https://mlsanity.com/paper/2410.20848/) (2024)
- [From Large Language Models and Optimization to Decision Optimization CoPilot: A Research Manifesto](https://mlsanity.com/paper/2402.16269/) (2024)
- [LLMs for Cold-Start Cutting Plane Separator Configuration](https://mlsanity.com/paper/2412.12038/) (2024)

## Built on by (most cited first, 9 of 9)

- [A Systematic Survey on Large Language Models for Evolutionary Optimization: From Modeling to Solving](https://mlsanity.com/paper/2509.08269/) (2025)
- [ORGEval: Graph-Theoretic Evaluation of LLMs in Optimization Modeling](https://mlsanity.com/paper/2510.27610/) (2025)
- [Large Language Models in Operations Research: Methods, Applications, and Challenges](https://mlsanity.com/paper/2509.18180/) (2025)
- [ORPilot: A Production-Oriented Agentic LLM-for-OR Tool for Optimization Modeling](https://mlsanity.com/paper/2605.02728/) (2026)
- [Grammar-Aware Literate Generative Mathematical Programming with Compiler-in-the-Loop](https://mlsanity.com/paper/2601.17670/) (2026)
- [MiniOpt: Reasoning to Model and Solve General Optimization Problems with Limited Resources](https://mlsanity.com/paper/2606.25832/) (2026)
- [FLARE: Verifying MILP Reformulations with LLM-Based Theorem Proving](https://mlsanity.com/paper/2608.25220/) (2026)
- [ModelEquivBench: Certifying Multi-Relational Evaluation of LLM-Generated Optimization Models](https://mlsanity.com/paper/2607.29431/) (2026)
- [SOVER: Formal Certification of Optimization Reformulations via LLM-Assisted SMT Verification](https://mlsanity.com/paper/2609.00728/) (2026)

## Abstract (arXiv)

A fundamental problem in combinatorial optimization is identifying equivalent formulations. Despite the growing need for automated equivalence checks -- driven, for example, by optimization copilots, which generate problem formulations from natural language descriptions -- current approaches rely on simple heuristics that fail to reliably check formulation equivalence. Inspired by Karp reductions, in this work we introduce Quasi-Karp equivalence, a formal criterion for determining when two optimization formulations are equivalent based on the existence of a mapping between their decision variables. We propose EquivaMap, a framework that leverages large language models to automatically discover such mappings for scalable, reliable equivalence checking, with a verification stage that ensures mapped solutions preserve feasibility and optimality without additional solver calls. To evaluate our approach, we construct EquivaFormulation, the first open-source dataset of equivalent optimization formulations, generated by applying transformations such as adding slack variables or valid inequalities to existing formulations. Empirically, EquivaMap significantly outperforms existing methods, achieving substantial improvements in correctly identifying formulation equivalence.