Agentic MIP 연구: 가속화된 제약 조건 핸들러 생성

혼합 정수 계획법 (MIP) 연구는 수학적으로도 복잡하고 공학적으로도 집약적입니다. 분기 및 절단(branch-and-cut) 솔버 내에서 알고리즘 가설을 테스트하려면 상당한 구현, 디버깅, 튜닝, 대규모 벤치마킹이 필요합니다. 우리는 LLM 에이전트를 솔버 인식 하니스에 임베딩하여 오픈 소스 솔버 SCIP의 플러그인을 생성, 검증 및 평가함으로써 이 피드백 루프를 단축하는 에이전트 기반 MIP 연구 프레임워크를 제안합니다. 전파(Propagation) 방법은 전역 제약 조건(global constraints)을 활용하여 MIP 해결을 가속화하는 데 핵심적인 역할을 합니다. 우리는 이 프레임워크를 MIP 공식화의 전역 제약 조건으로의 의미론적 리프팅과 전파 전용 SCIP 제약 조건 핸들러의 자동 구축에 적용합니다. MIPLIB 2017 벤치마크 세트에서, 이 프레임워크는 제약 조건 프로그래밍으로부터 전역 제약 조건 구조를 성공적으로 복구하고 실행 가능한 제약 감지기(constraint detectors)와 전파 전용 제약 조건 핸들러를 생성합니다. 나아가, 이 프레임워크는 샌드박스 환경 내의 인컨텍스트 학습(in-context learning)으로 자연스럽게 확장되어, 에이전트가 실제 인스턴스에서 생성된 제약 조건 핸들러를 튜닝하고 디버깅할 수 있게 할 뿐만 아니라, MIP 문제에서 전역 제약 조건 패턴을 탐색하고 SCIP에 아직 구현되지 않은 새로운 전파 전략을 발견할 수 있도록 합니다.

이 프레임워크는 의미 있는 알고리즘적 개선 사항을 가치 낮거나 과도하게 비용이 많이 드는 후보들과 체계적으로 구별할 수 있게 합니다. 새로 개발된 전파(propagation) 방법들은 탐색된 벤치마크 내에서 추가로 다섯 개의 인스턴스를 성공적으로 해결했습니다. 전반적으로, 이 프레임워크는 LLM 에이전트가 복잡한 MIP 연구 루프를 자율적으로 탐색할 수 있음을 입증하며, 보다 자동화된 솔버 개발 프로세스의 길을 열어줍니다.