arXiv:2608.25220v1 cs.AI

FLARE: LLM 기반 정리 증명을 통한 MILP 재공식화 검증

FLARE: Verifying MILP Reformulations with LLM-Based Theorem Proving

Henry Robbins, Connor Lawless, Madeleine Udell, Ellen Vitercik

제출 2026-08-25

한국어 초록

혼합정수 선형 계획(MILP)은 광범위한 실세계 응용을 갖는 조합 최적화의 기본 도구이다. 핵심 과제는 계산적으로 효율적인 MILP 공식화(formulation)를 설계하는 것이다. 대규모 언어 모델(LLM)은 공식화 도출에서 강화까지 모델링 과정을 자동화할 새로운 기회를 제공한다. 신뢰할 수 있는 자동화는 제안된 공식화가 근본 최적화 문제를 보존하는지 검증하는 견고한 방법을 요구한다. 그러나 기존 접근법은 공식화를 수치적으로만 평가하며 일반적인 문제 인스턴스에 대해 추론하지 못한다. 우리는 Lean에서 형식화하고 기계 검증할 수 있는 MILP 재공식화(reformulation)의 구성적 정의를 도입하여 이 한계를 해결한다. 우리는 제안된 재공식화를 기준 공식화(reference formulation)에 대해 검증하기 위해 LLM 기반 에이전트와 Lean 증명 보조 도구(proof assistant)를 사용하는 방법인 FLARE(Formulation-Level Automated Reformulation Evaluation)를 개발한다. 접근법을 평가하기 위해 20개 문제와 109개 공식화로 구성된 도전적인 데이터셋 FormulationBench를 도입한다. FLARE는 기존 방법을 능가하며, FormulationBench의 NP-hard 부분집합에서 100% 정확도를 달성한다. 또한 FLARE는 수락하는 모든 재공식화에 대해 기계 검증 가능한 증명서(certificate)를 생성한다. 형식적 보장이 필요 없는 경우, FLARE와 동일한 정확도를 갖지만 증명서를 생성하지 않는 빠르고 저렴한 LLM 프록시 FLARE-NL을 도입한다. 이 방법들은 자동화된 최적화 모델링에서 신뢰할 수 있는 검증을 가능하게 한다.

원문 초록

Mixed-Integer Linear Programming (MILP) is a fundamental tool for combinatorial optimization with extensive real-world applications. A central challenge is designing computationally efficient MILP formulations. Large Language Models (LLMs) offer new opportunities to automate the modeling process, from deriving formulations to strengthening them. Reliable automation requires robust methods for verifying that proposed formulations preserve the underlying optimization problem. However, existing approaches evaluate formulations numerically and fail to reason about general problem instances. We resolve this limitation by introducing a constructive definition of MILP reformulation that can be formalized in Lean and machine-checked. We develop FLARE (Formulation-Level Automated Reformulation Evaluation), a method that uses an LLM-based agent and the Lean proof assistant to verify proposed reformulations against a reference formulation. To evaluate our approach, we introduce FormulationBench, a challenging dataset of 20 problems and 109 formulations. FLARE outperforms existing methods, with 100% accuracy on the NP-hard subset of FormulationBench. Furthermore, FLARE produces a machine-checkable certificate for every reformulation it accepts. For cases where formal guarantees are not necessary, we introduce FLARE-NL, a fast and cheap LLM proxy that matches FLARE's accuracy but produces no certificate. These methods enable reliable verification in automated optimization modeling.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2608.25220v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.