조합 최적화 문제를 위한 비현실성 인지 대규모 언어 모델

Infeasibility Aware Large Language Models for Combinatorial Optimization

대규모 언어 모델(LLM)은 NP-hard 조합 최적화 문제에 대해 점점 더 많이 활용되고 있지만, 대부분의 기존 방법은 실행 가능한 인스턴스 솔루션 생성에 중점을 두고 명시적으로 비현실성 감지를 다루지 않습니다. 본 논문에서는 인증된 데이터셋 구축, 지도 학습 및 LLM 지원 하위 검색을 결합한 비현실성 인지 프레임워크를 제안합니다. 마이너 임베딩 문제의 경우, 새로운 수학적 프로그래밍 모델과 함께 증명 가능한 제로 페이즈 비현실성 검사를 도입하여, 구조화된 증명과 함께 실행 가능하다고 레이블링되거나 인증된 비현실성으로 레이블링되는 학습 인스턴스를 확장 가능하게 구축할 수 있습니다. 이 정확한 최적화 파이프라인을 통해 생성된 학습 데이터를 사용하여, 80억 개의 파라미터를 가진 LLM을 미세 조정하여 솔루션 생성과 비현실성 감지를 동시에 수행할 수 있음을 보여줍니다. 또한, LLM의 출력을 하위 로컬 검색의 초기값으로 활용하여, LLM의 출력이 완벽하지 않더라도 최적화를 가속화하는 실용적인 방법을 제공합니다. 실험 결과, 미세 조정된 모델은 GPT-5.2에 비해 전체 정확도를 최대 30% 향상시키는 것으로 나타났으며, LLM 기반 초기값은 하위 로컬 검색에서 처음부터 시작하는 것보다 최대 2배 빠른 속도를 제공합니다.

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\times$ speedup compared with starting from scratch in downstream local search.