혼합 정수 선형 및 비선형 프로그래밍에서의 자동 연구
Autoresearch in Mixed-Integer Linear and Nonlinear Programming
한국어 초록
자동 연구(autoresearch)의 최근 발전에도 불구하고, 전형적으로 NP-난해(NP-hard) 혼합 정수 선형 또는 비선형 프로그램(MILP 또는 MINLP)으로 공식화되는 실제 운영 연구(operations research) 문제에 이를 적용하는 것은 여전히 어렵습니다. 효과적인 연구를 위해서는 상충하는 아이디어들과 장기적(long-horizon) 실험 궤적을 체계적으로 관리해야 하기 때문입니다. 본 논문에서는 아이디어 풀링(pooling)과 알고리즘 트리 탐색을 통해 혼합 정수 프로그래밍에서 장기적 자동 연구를 체계화하는 재사용 가능한 에이전트(agent) 스킬인 AutoMIP을 소개합니다. AutoMIP은 상호보완적인 후보 아이디어들의 지속적인 풀을 유지하는 동시에 실행 가능한 실험들을 알고리즘 트리로 구성하여, 에이전트가 탐색되지 않은 가설을 보존하고 유망한 알고리즘을 개선하며 과거 상태를 기반으로 대안적 방법론 방향으로 전환할 수 있도록 지원합니다. MILP 및 MINLP 벤치마크(benchmark) 코호트에서 AutoMIP은 평가된 자동 연구 프레임워크 중 가장 높은 최종 성공률을 달성했습니다. MIPLib에서 AutoMIP은 60개 인스턴스 중 31개에서 새로운 최적해를 발견하여 기존 자동 연구 프레임워크를 능가했습니다. MINLPLib에서는 60개 인스턴스 중 52개에서 새로운 최적해를 달성했습니다. 절제 연구(ablation study)는 아이디어 풀링과 알고리즘 트리 탐색의 상호보완적 기여를 추가로 입증하며, 장기적 자동 연구를 위해 다양한 연구 아이디어와 구조화된 실험 궤적을 함께 유지하는 것의 중요성을 강조합니다.
원문 초록
Despite recent progress in autoresearch, applying it to practical operations research problems, typically formulated as NP-hard mixed-integer linear or nonlinear programs (MILPs or MINLPs), remains challenging because effective research requires systematically managing competing ideas and long-horizon experimental trajectories. We introduce AutoMIP, a reusable agent skill for organizing long-horizon autoresearch in mixed-integer programming through idea pooling and algorithm tree search. AutoMIP maintains a persistent pool of complementary candidate ideas while organizing executable experiments into an algorithm tree, enabling the agent to preserve unexplored hypotheses, refine promising algorithms, and switch to alternative methodological directions based on historical states. On MILP and MINLP benchmark cohorts, AutoMIP achieves the highest final success rates among the evaluated autoresearch frameworks. On MIPLib, AutoMIP discovers new best solutions for 31 of 60 instances, surpassing existing autoresearch frameworks. On MINLPLib, it achieves new best solutions for 52 of 60 instances. Ablation studies further demonstrate the complementary contributions of idea pooling and algorithm tree search, highlighting the importance of jointly maintaining diverse research ideas and structured experimental trajectories for long-horizon autoresearch.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
텍스트 비즈니스 입력을 활용한 LLM 기반 교통 허브 용량 계획
LLM-Guided Transportation Hub Capacity Planning with Textual Business Inputs
전통적인 허브 용량 계획 모델은 정량적 입력에 대해 효과적으로 최적화하지만, 정성적인 비즈니스 맥락을 소화하는 데에는 종종 실패한다. 본 논문에서는 대규모 언어 모델(LLM) 에이전트가 자연어 비즈니스 맥락 설명을 바탕으로 허브 용량 결정을 반복적으로 제안하는 새로운 프레임워크를 제안한다. 핵심 메커니즘은 사고의 연쇄(Chain-of-Thought) 추론 프로토콜로, LLM은 함축된 변화의 방향과 크기를 기반으로 각 맥락 항목을 구체적인 용량 조정에 매핑하는 구조화된 의사결정 테이블을 구성한다. 이후 새로운 용량 결정은 에이전트의 선택을 유도하기 위해 경로 지정 기반 성능 지표를 제공하는 최적화 모델과의 피드백 루프를 통해 검증된다. 미국 남동부의 실제 13개 허브 화물 네트워크에서 본 프레임워크는 숨겨진 실제 정답(ground-truth) 대비 2.8%의 최적성 갭(optimality gap)을 달성하여, 텍스트 비즈니스 입력이 없는 전통적인 최적화 모델이 보인 11.0%의 갭에 비해 상당한 개선을 이루었다. 이는 LLM이 정성적 비즈니스 인사이트를 운영 연구(Operations Research) 워크플로우에 통합하는 맥락적 가교 역할을 할 수 있음을 보여준다.
OR을 수행하는 AI를 위한 OR: OSCAR 프레임워크 내에서 에스컬레이터를 따라 LLM 라우팅하기
OR for AI That Does OR: Routing LLMs up the Escalator inside the OSCAR Framework
대규모 언어 모델(LLM)은 비즈니스 설명을 최적화 모델(optimization model)로 변환할 수 있지만, 실행 가능한 코드가 제약 조건이나 목적 함수를 잘못 나타낼 수 있습니다. 이 경우 솔버(solver)는 잘못된 문제에 대한 최적해를 반환할 수 있습니다. 해당 해가 의도한 운영 규칙을 만족하더라도 더 나은 계획이 존재할 수 있습니다. 최적화 모델링을 반복적으로 사용하는 조직의 경우, LLM 기반 프레임워크는 저비용으로 정확한 수식화를 생성해야 하며 이상적으로는 로컬에서 실행되어야 합니다. 본 연구에서는 개선 사항을 검증하고 가격 및 성능이 서로 다른 LLM 간에 시도를 어떻게 할당할지 연구합니다. 우리는 라벨링된 결정 예시를 바탕으로 검증된 오프라인 시뮬레이터(Simulator)를 사용하여 후보들을 비교하고 단순 실행 가능성을 넘어 탐색을 지속하는 OSCAR(Optimization modeling by Simulator, Coder, And Reviewer)를 개발합니다. 우리는 다음으로 검증된 개선안을 찾는 과정을 관측되지 않은 난이도 하에서의 순차적 의사결정(어떤 LLM을 호출하고 언제 중단할지)으로 모델링합니다. 사전 확률이 알려진 단순화된 환경에서 비용 순서에 따른 에스컬레이션(cost-ordered escalation)이 최적이 되는 조건을 제시합니다. 일반적인 메뉴에 대해서는 사전 확률에 구애받지 않는(prior-free) 경쟁적 보장을 도출합니다. 5개의 벤치마크 문제에서 OSCAR는 단일 GPU에 로컬 배포 가능한 두 개의 소형 오픈 가중치(open-weight) LLM을 사용하여 보고된 설정 기준 95%에서 100%의 정확도를 달성합니다. 이 모델들의 단일 시도 정확도는 평균 29% 및 48%입니다. 문제당 5회 실행에서 Codex와 Claude Code는 OSCAR에 비해 각각 평균 3.1배, 5.8배의 토큰 비용을 발생시킵니다. OSCAR는 예산 및 기밀성 요구사항에 따라 로컬 또는 클라우드에서 오픈 가중치 모델을 지원합니다. 기업은 자연어 운영 규칙을 명확히 하기 위해 실행 가능한 결정과 실행 불가능한 결정에 대한 라벨링된 결정 예시를 유지 관리해야 합니다. OSCAR는 LLM의 해석이 이들과 충돌할 때 이러한 라벨을 따릅니다. LLM 성능과 가격이 변화함에 따라, OSCAR의 단순한 운영 규칙과 조정 가능한 설정은 기업이 모델 선택을 적응시키고 이러한 발전을 활용할 수 있도록 돕습니다.
OptiSkill: LLM 기반 최적화 모델링을 위한 계층적·진화형 SkillBank
OptiSkill: A Hierarchical and Evolving SkillBank for LLM-Based Optimization Modeling
자동화된 운영연구(OR) 모델링은 LLM이 자연어 의사결정 문제를 올바른 수학적 프로그램으로 변환할 것을 요구한다. 기존 방법은 개별 공식화(formulation)를 개선할 수 있지만, 종종 문제를 고립하여 해결하여 재사용 가능한 경험을 거의 남기지 못하고 유사한 공식화 오류를 반복한다. 선행 메모리 기반 접근법은 예시, 사고, 또는 인사이트를 참조로 저장하는 반면, OR 모델링은 문제 서사에 걸쳐 전이되는 재사용 가능한 공식화 skill이 필요하며 구체적인 모델링 결정을 안내한다. 우리는 LLM 기반 OR 모델링을 위해 계층적이고 진화하는 SkillBank를 구축하는 skill-증강 프레임워크인 OptiSkill을 제안한다. SkillBank는 solver로 검증된 경험을 재사용 가능한 skill로 저장하며, 문제 수준 공식화 골격을 위한 Global Strategies와 지역적 오류 방지 규칙을 위한 Step Experiences를 둔다. 이는 안정적인 배치 수준 테스트 시간(test-time) 진화를 통해 더 정제되며, 후보 skill은 검증 후에만 통합된다. 8개 OR 모델링 벤치마크에서의 실험은 OptiSkill이 다양한 LLM 백본에서 공식화 정확도를 개선하고, 강력한 에이전트(agentic) baseline을 능가하며, SkillBank의 커버리지와 신뢰성을 확장함으로써 추가 이득을 얻음을 보여준다. 코드와 데이터는 https://github.com/rachhhhing/OptiSkill 에서 이용 가능하다.
부하 의존 비용을 갖는 중국인 우편배달부 문제를 위한 하이브리드 메타휴리스틱 프레임워크
A Hybrid Matheuristic Framework for the Chinese Postman Problem with Load-Dependent Costs
부하 의존 비용을 갖는 중국인 우편배달부 문제(CPP-LC)는 이동 비용이 차량 부하와 에너지 소비에 따라 달라지는 실제 물류 및 운송 시스템에서 발생한다. 본 연구에서는 CPP-LC를 효율적으로 풀기 위해 메타휴리스틱 탐색과 수학적 계획법(mathematical programming)을 통합한 하이브리드 최적화 프레임워크를 제안한다. 제안 방법은 탐험과 집중(intensification)의 균형을 맞추기 위해 지역 탐색 절차와 축소된 혼합정수 선형 계획(MILP) 모델을 결합한다. 또한 대규모 인스턴스에서 확장성을 높이기 위해 개미 군집 최적화(ACO) 알고리즘을 개발한다. 벤치마크 데이터셋에 대한 광범위한 실험 결과, 제안 프레임워크가 일관되게 고품질 해를 달성하고 계산 효율성을 유지하면서 기존 접근법보다 해의 품질에서 우수한 성능을 보임을 보여준다. 이러한 결과는 실용적 응용에서 복잡한 부하 의존 경로 문제에 대한 하이브리드 최적화 전략의 효과를 부각한다. 구현체는 https://github.com/HySonLab/MatCPP 에서 공개적으로 제공된다.
컬럼 생성 안정화를 위한 학습 기반 쌍별 심층 이중 최적 부등식
Learned Pairwise Deep Dual-Optimal Inequalities for Stabilizing Column Generation
컬럼 생성(CG)은 차량 경로 문제에 대한 분기-가격-절단(branch-price-and-cut) 방법을 포함하여 많은 대규모 최적화 알고리즘의 핵심이지만, 불안정한 이중(dual) 해는 수렴을 상당히 느리게 할 수 있다. 기존의 심층 이중 최적 부등식은 이중 공간을 제한함으로써 이러한 불안정성을 줄일 수 있다. 그러나 그 구성은 일반적으로 용량 제한, 시간 창, 기타 자원 제약이 있는 경로 문제에 대해 확립하기 어려운 문제 특화 교환 논증에 의존한다. 본 연구에서는 이중 변수 간 쌍별 순서 관계를 예측하고 그 원 문제(primal) 대응 항을 마스터 문제에 직접 통합하는 학습 프레임워크인 학습 기반 쌍별 심층 이중 최적 부등식(L-PDDOIs)을 제안한다. 학습 라벨을 구성하기 위해, 이 프레임워크는 최적 이중 해를 샘플링하고 샘플의 충분히 큰 공통 부분집합에서 동시에 성립하는 쌍별 순서 관계를 선택한다. 분류기는 각 후보 관계에 점수를 부여한다. 예측된 관계 간의 충돌과 중복이 성능을 저해할 수 있으므로, 그래프 기반 후처리가 배포 전에 후보 집합을 필터링하고 압축한다. 또한 선택적으로 학습된 부등식을 완화하고 기준선 CG 경계가 복원되었을 때 이를 증명하는 복구 절차를 도입한다. 용량 제한 차량 경로 문제와 시간 창 차량 경로 문제의 주요 테스트 세트에서 L-PDDOIs를 직접 배포하면 기하평균 루트 CG 시간이 각각 89.7% 및 93.9% 감소하는 반면, 평균 경계 손실은 각각 1.3% 및 0.5%에 불과하다. 복구 절차는 CG 경계의 손실 없이 보장하면서 각각 54.8% 및 83.1%의 해당 시간 감소를 유지한다.
교통 관리를 위한 비용 최적 파운데이션 모델 배포 포트폴리오
Cost-Optimal Foundation Model Deployment Portfolio for Transportation Management
파운데이션 모델(foundation model)에는 대규모 언어 모델(LLM)과 비전-언어 모델(VLM)이 포함되며, 이상 탐지, 사고 보고, 여행자 정보 제공과 같은 교통 관리 센터(TMC) 업무에 점점 더 많이 사용되고 있다. 여러 이러한 모델을 TMC 기능 전반에 배포하는 것은 포트폴리오 질문을 제기한다: 각 기능에 어떤 모델이, 어떤 배포 모드로, 그리고 어떤 공유 하드웨어 예산 하에서 제공되어야 하는가? 우리는 이를 파운데이션 모델 배포 포트폴리오(FMDP) 문제로 공식화한다. 이는 공유 GPU 용량에 대해 기능별 품질, 지연 시간, 안전성 제약을 만족하면서 총 소유 비용(TCO)을 최소화하는 혼합 정수 프로그램이다. 0-1 배낭 문제로의 환원을 통해 이 문제가 NP-난해함을 증명하고, 다항 시간 탐욕적 휴리스틱을 제안한다. 다섯 가지 TMC 기능과 19개의 후보 (모델, 모드) 쌍을 포함한 예시 사례 연구에서, FMDP는 4개 기능을 오픈소스 API로, 오픈소스 모델이 품질 하한을 충족하지 못하는 1개 기능을 폐쇄형 API로 라우팅하는 혼합 포트폴리오를 식별하여 월 $34(가장 저렴한 실행 가능한 전체 폐쇄형 API 기준선 대비 97% 절감)의 비용을 산출한다. 손익분기 분석에 따르면, 온프레미스 GPU 투자는 시간당 약 309회의 비전 쿼리 이상이거나 API 가격이 두 배로 오를 때만 합리적이 된다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.