# Infeasibility Aware Large Language Models for Combinatorial Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 49 references that are in the map.
- First posted on arXiv 1 Apr 2026.

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

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents](https://mlsanity.com/paper/2201.07207/) (2022)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Large Language Models as Evolutionary Optimizers](https://mlsanity.com/paper/2310.19046/) (2023)
- [ORLM: A Customizable Framework in Training Large Models for Automated Optimization Modeling](https://mlsanity.com/paper/2405.17743/) (2024)
- [SatLM: Satisfiability-Aided Language Models Using Declarative Prompting](https://mlsanity.com/paper/2305.09656/) (2023)
- [LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch](https://mlsanity.com/paper/2410.13213/) (2024)
- [Algorithm Discovery With LLMs: Evolutionary Search Meets Reinforcement Learning](https://mlsanity.com/paper/2504.05108/) (2025)
- [OptiMUS: Optimization Modeling Using MIP Solvers and large language models](https://mlsanity.com/paper/2310.06116/) (2023)
- [OptiMUS-0.3: Using Large Language Models to Model and Solve Optimization Problems at Scale](https://mlsanity.com/paper/2407.19633/) (2024)
- [SATBench: Benchmarking LLMs' Logical Reasoning via Automated Puzzle Generation from SAT Formulas](https://mlsanity.com/paper/2505.14615/) (2025)
- [Large Language Models as End-to-end Combinatorial Optimization Solvers](https://mlsanity.com/paper/2509.16865/) (2025)
- [Diagnosing Infeasible Optimization Problems Using Large Language Models](https://mlsanity.com/paper/2308.12923/) (2023)
- [A practical heuristic for finding graph minors](https://mlsanity.com/paper/1406.2741/) (2014)
- [Large Language Models for Combinatorial Optimization: A Systematic Review](https://mlsanity.com/paper/2507.03637/) (2025)
- [Can Transformers Reason Logically? A Study in SAT Solving](https://mlsanity.com/paper/2410.07432/) (2024)
- [Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition](https://mlsanity.com/paper/2504.03930/) (2025)
- [Fast clique minor generation in Chimera qubit connectivity graphs](https://mlsanity.com/paper/1507.04774/) (2015)
- [DiLA: Enhancing LLM Tool Learning with Differential Logic Layer](https://mlsanity.com/paper/2402.11903/) (2024)
- [Integer programming techniques for minor-embedding in quantum annealers](https://mlsanity.com/paper/1912.08314/) (2019)
- [Minor Embedding for Quantum Annealing with Reinforcement Learning](https://mlsanity.com/paper/2507.16004/) (2025)

## Abstract (arXiv)

Large language models (LLMs) are increasingly explored for NP-hard combinatorial optimization problems, but most existing methods emphasize feasible-instance solution generation and do not explicitly address infeasibility detection. We propose an infeasibility-aware framework that combines certifiable dataset construction, supervised fine-tuning, and LLM-assisted downstream search. For the minor-embedding problem, we introduce a new mathematical programming formulation together with provable zero-phase infeasibility screening, which enables scalable construction of training instances labeled either as feasible with structured certificates or as certifiably infeasible. Using training data generated through this exact optimization pipeline, we show that an 8B-parameter LLM can be fine-tuned to jointly perform solution generation and infeasibility detection. We further utilize LLM outputs as warm starts for downstream local search, providing a practical way to accelerate optimization even when the LLM outputs are imperfect. Experiments show that our fine-tuned model improves overall accuracy by up to 30% over GPT-5.2; meanwhile LLM-guided warm starts provide up to 2× speedup compared with starting from scratch in downstream local search.