Daily Arxiv

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

Discovering Heuristics with Large Language Models (LLMs) for Mixed-Integer Programs: Single-Machine Scheduling

Created by
  • Haebom

저자

Ibrahim O\u{g}uz \c{C}etinkaya, I. Esra Buyuktahtak{\i}n, Parshin Shojaee, Chandan K. Reddy

개요

본 연구는 대규모 언어 모델(LLM)의 힘을 활용하여 발견된 새로운 휴리스틱을 통해 스케줄링 및 조합 최적화 문헌에 기여합니다. 단일 기계 총 지연 시간(SMTT) 문제를 해결하기 위해, LLM 기반의 EDD Challenger(EDDC) 및 MDD Challenger(MDDC) 두 가지 새로운 휴리스틱을 개발하고 벤치마킹합니다. EDDC와 MDDC는 각각 Earliest Due Date(EDD) 및 Modified Due Date(MDD) 규칙에서 영감을 받았습니다. 최적성 갭과 솔루션 시간을 포함한 엄격한 기준을 사용하여 알고리즘을 평가하고, 다양한 작업 크기(20, 100, 200, 500개 작업)에서 기존 휴리스틱 및 정확한 방법과 성능을 비교합니다.

시사점, 한계점

LLM을 활용한 새로운 휴리스틱 개발: EDDC와 MDDC는 SMTT 문제 해결을 위한 새로운 휴리스틱으로, EDD 및 MDD 규칙을 기반으로 LLM을 통해 발견되었습니다.
성능 우수성: MDDC는 전통적인 휴리스틱보다 일관적으로 우수한 성능을 보이며, 특히 대규모 문제에서 정확한 방법과 경쟁할 만한 수준을 보입니다. EDDC는 EDD 규칙 및 기존 알고리즘보다 개선된 성능을 보여줍니다.
확장성: 본 연구는 인간-LLM 협업이 NP-hard 제약 조건이 있는 조합 최적화 문제에 대해 확장 가능한 고성능 휴리스틱을 생성할 수 있음을 보여줍니다.
계산 복잡성: 100개 이상의 작업 인스턴스에서는 MIP 및 동적 프로그래밍과 같은 정확한 방법의 계산 복잡성이 증가합니다.
리소스 제약: 효과적인 구성 하에서 제한된 리소스로도 LLM을 활용하여 우수한 성능을 얻을 수 있습니다.
👍