{"id":"arxiv/2604.01455","url":"https://arxiv.org/abs/2604.01455","tags":["cs.AI","cs.LG","quant-ph"],"score":0,"title":"Infeasibility Aware Large Language Models for Combinatorial Optimization","domain":"cs.AI","source":"arxiv","authors":["Yakun Wang","Min Chen","Zeguan Wu","Junyu Liu","Sitao Zhang","Zhenwen Shao"],"reviews":0,"subject":"cs.AI","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-01","reactions":{}}