GES(Graph Edge Sparsification)는 유클리드 TSP를 위한 학습 기반 그래프 간선 희소화 기법으로, 고정 휴리스틱에 의존하던 기존 방법과 달리 인스턴스별 기하 구조 정보를 활용해 적응적으로 희소 그래프를 생성한다. MATILDA 데이터셋에서 간선의 최대 95%를 제거하면서도 해 품질 격차를 최적값 대비 1% 이내로 유지했다. TSPLIB 벤치마크에서도 강한 일반화 성능을 보였고, 일부 대규모 인스턴스에서는 99% 이상을 가지치기하면서 최적성 격차 1% 미만을 달성했다. 대규모 조합최적화 문제의 정확해 계산 비용을 크게 낮출 수 있는 실용적 전처리 기법이다.
- •기하 구조 정보와 조합최적화 기술을 결합해 인스턴스별로 적응적 희소 그래프를 생성하는 학습 기반 접근
- •MATILDA 데이터셋에서 간선 최대 95% 제거에도 해 품질 격차 1% 이내 유지
- •TSPLIB 일부 대규모 인스턴스에서 99% 이상 가지치기에도 최적성 격차 1% 미만으로 강한 일반화 입증
GES-TSP: Graph Edge Sparsification for TSP
본문 미리보기
arXiv:2607.09708v1 Announce Type: new Abstract: Solving large-scale instances of the Traveling Salesman Problem (TSP) exactly is computationally expensive. Researchers often employ graph sparsification methods to improve computational efficiency. Traditional sparsification methods typically rely on fixed heuristics and fail to fully exploit instance-specific structural information. In this paper, we propose Graph Edge Sparsification (GES), a learning-based sparsification approach for Euclidean
전체 내용이 궁금하다면?
원문을 직접 읽어보세요