목적 함수 등가성을 넘어: 차량 경로 문제(VRP)에서의 LLM 기반 최적화 모델링을 위한 제약 조건 주입 (Constraint

대규모 언어 모델 (LLMs)은 자연어 최적화 문제를 실행 가능한 솔버 (solver) 코드로 번역하는 능력을 점점 더 높여가고 있습니다. 그러나 제약 조건이 밀집된 운영 연구 (OR) 문제의 경우, 기존의 데이터 필터링 및 학습 파이프라인은 주로 차분 테스트 (differential testing) 및 정답 일치와 같은 목적 함수 등가성 (objective-equivalence) 신호에 크게 의존합니다. 이러한 신호는 제약 조건이 테스트 인스턴스에 대해 비구속적 (non-binding)일 때, 프로그램이 가짜 제약 조건을 추가하거나 필수 제약 조건을 조용히 누락하더라도 통과할 수 있다는 문제가 있습니다. 우리는 가짜 과잉 제약 (spurious over-constraint)을 드러내기 위해 실행 가능한 프로브 (feasible probes)를 사용하고, 조용한 제약 조건 누락 (silent constraint omission)을 밝혀내기 위해 하나의 제약 조건을 위반하는 프로브 (one-constraint-violating probes)를 사용하는 제약 조건 주입 (constraint injection) 방식을 제안합니다. 이는 차분 테스트와 결합되어 이중 검증기 (dual verifier)를 형성합니다. 우리는 결합된 운영 제약 조건을 가진 대표적인 제약 밀집 조합 최적화 테스트베드인 차량 경로 문제 (VRPs)에서 이를 구현하고 평가합니다. 우리는 자연어 VRP 시나리오를 Gurobi 스크립트로 번역하는 8B 엔드 투 엔드 (end-to-end) 모델인 VRPCoder와, 21가지 변형을 다루는 전문가 검증 VRP 벤치마크 제품군을 개발했습니다. 이 검증기는 데이터 합성 중에는 거부 샘플링 (rejection-sampling) 필터로, 그룹 상대적 정책 최적화 (GRPO)에서는 롤아웃당 보상 (per-rollout reward)으로 재사용됩니다. 4개의 VRP 벤치마크 전반에 걸쳐 VRPCoder-GRPO는 평균 93%의 Pass@1을 달성하였으며, 3개의 벤치마크에서 Gemini-3.1-Pro Preview를 능가하고, Claude-Sonnet-4.5보다 평균 28포인트 높으며, 이전의 OR-LLM들보다 평균 78포인트 앞서는 성능을 보여주었습니다.