Daily Arxiv

전 세계에서 발간되는 인공지능 관련 논문을 정리하는 페이지 입니다.
본 페이지는 Google Gemini를 활용해 요약 정리하며, 비영리로 운영 됩니다.
논문에 대한 저작권은 저자 및 해당 기관에 있으며, 공유 시 출처만 명기하면 됩니다.

Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problem

작성자
  • Haebom

저자

Junyang Cai, Serdar Kadioglu, Bistra Dilkina

개요

본 논문은 사전 훈련 없이 온라인 학습 기능을 갖춘 MIP(Mixed-integer programming)용 적응형 메타 솔버인 Balans를 제안한다. Balans는 MIP 솔버 위에서 작동하는 적응형 대규모 근린 탐색(large-neighborhood search) 기반으로, 파괴 및 복구 근린 연산자를 반복적으로 적용한다. 다양한 근린 정의 중 선택은 멀티암드 밴딧 알고리즘을 통해 인스턴스에 따라 실시간으로 이루어진다. 실험 결과, Balans는 기본 MIP 솔버보다 성능이 뛰어나며, 단일 최적 근린에 고정하는 것보다 우수하고, 최첨단 MIP용 대규모 근린 탐색보다 향상된 성능을 보였다. Balans는 고도로 구성 가능하고 MIP 솔버와 독립적인 오픈소스 소프트웨어로 공개된다.

시사점, 한계점

시사점:
사전 훈련 없이 온라인 학습으로 MIP 문제 해결 속도 향상 가능성 제시.
다양한 근린 정의 중 최적 선택을 위한 멀티암드 밴딧 알고리즘의 효과적인 적용.
기존 MIP 솔버 및 대규모 근린 탐색 기법보다 우수한 성능을 보임.
오픈소스 소프트웨어 공개를 통한 접근성 향상 및 연구 확장 가능성 제시.
한계점:
특정 유형의 MIP 문제에 대한 일반화 성능은 추가 연구가 필요할 수 있음.
멀티암드 밴딧 알고리즘의 매개변수 조정에 대한 추가적인 연구가 필요할 수 있음.
대규모 문제에 대한 확장성에 대한 추가적인 검증이 필요할 수 있음.
👍