# Hard Constraints Meet Soft Generation: Guaranteed Feasibility for LLM-based Combinatorial Optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 32 references that are in the map.
- First posted on arXiv 1 Feb 2026.

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

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [SimPO: Simple Preference Optimization with a Reference-Free Reward](https://mlsanity.com/paper/2405.14734/) (2024)
- [A General Theoretical Paradigm to Understand Learning from Human Preferences](https://mlsanity.com/paper/2310.12036/) (2023)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Progressive-Hint Prompting Improves Reasoning in Large Language Models](https://mlsanity.com/paper/2304.09797/) (2023)
- [Large Language Models as Evolutionary Optimizers](https://mlsanity.com/paper/2310.19046/) (2023)
- [Grammar-Aligned Decoding](https://mlsanity.com/paper/2405.21047/) (2024)
- [Evolution Strategies at Scale: LLM Fine-Tuning Beyond Reinforcement Learning](https://mlsanity.com/paper/2509.24372/) (2025)
- [Large Language Models as End-to-end Combinatorial Optimization Solvers](https://mlsanity.com/paper/2509.16865/) (2025)
- [Self-Guiding Exploration for Combinatorial Problems](https://mlsanity.com/paper/2405.17950/) (2024)
- [Safety Filtering While Training: Improving the Performance and Sample Efficiency of Reinforcement Learning Agents](https://mlsanity.com/paper/2410.11671/) (2024)
- [SEFRQO: A Self-Evolving Fine-Tuned RAG-Based Query Optimizer](https://mlsanity.com/paper/2508.17556/) (2025)
- [Bridging Synthetic and Real Routing Problems via LLM-Guided Instance Generation and Progressive Adaptation](https://mlsanity.com/paper/2511.10233/) (2025)
- [Decision-focused Graph Neural Networks for Combinatorial Optimization](https://mlsanity.com/paper/2406.03647/) (2024)
- [End-to-end Deep Reinforcement Learning for Stochastic Multi-objective Optimization in C-VRPTW](https://mlsanity.com/paper/2512.01518/) (2025)

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

- [TriVAL: A Tri-Validation Framework for Faithful Automatic Optimization Modeling](https://mlsanity.com/paper/2605.23966/) (2026)
- [Linear Temporal Logic Translation via Human-Inspired Self-Constrained Reasoning for Robot Task Specification](https://mlsanity.com/paper/2608.28435/) (2026)
- [VLM Fine-Tuning for End-to-End Combinatorial Optimization](https://mlsanity.com/paper/2609.37175/) (2026)

## Abstract (arXiv)

Large language models (LLMs) have emerged as promising general-purpose solvers for combinatorial optimization (CO), yet they fundamentally lack mechanisms to guarantee solution feasibility which is critical for real-world deployment. In this work, we introduce FALCON, a framework that ensures 100% feasibility through three key innovations: (i) grammar-constrained decoding enforces syntactic validity, (ii) a feasibility repair layer corrects semantic constraint violations, and (iii) adaptive Best-of-N sampling allocates inference compute efficiently. To train the underlying LLM, we introduce the Best-anchored Objective-guided Preference Optimization (BOPO) in LLM training, which weights preference pairs by their objective gap, providing dense supervision without human labels. Theoretically, we prove convergence for BOPO and provide bounds on repair-induced quality loss. Empirically, across seven NP-hard CO problems, FALCON achieves perfect feasibility while matching or exceeding the solution quality of state-of-the-art neural and LLM-based solvers.