GES(Graph Edge Sparsification)는 유클리드 TSP를 위한 학습 기반 그래프 간선 희소화 기법으로, 고정 휴리스틱에 의존하던 기존 방법과 달리 인스턴스별 기하 구조 정보를 활용해 적응적으로 희소 그래프를 생성한다. MATILDA 데이터셋에서 간선의 최대 95%를 제거하면서도 해 품질 격차를 최적값 대비 1% 이내로 유지했다. TSPLIB 벤치마크에서도 강한 일반화 성능을 보였고, 일부 대규모 인스턴스에서는 99% 이상을 가지치기하면서 최적성 격차 1% 미만을 달성했다. 대규모 조합최적화 문제의 정확해 계산 비용을 크게 낮출 수 있는 실용적 전처리 기법이다.
- •기하 구조 정보와 조합최적화 기술을 결합해 인스턴스별로 적응적 희소 그래프를 생성하는 학습 기반 접근
- •MATILDA 데이터셋에서 간선 최대 95% 제거에도 해 품질 격차 1% 이내 유지
- •TSPLIB 일부 대규모 인스턴스에서 99% 이상 가지치기에도 최적성 격차 1% 미만으로 강한 일반화 입증
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
GES-TSP: Graph Edge Sparsification for TSP
- 1.GES 제안: 유클리드 TSP용 학습 기반 그래프 엣지 희소화로 인스턴스별 적응적 가지치기
- 2.MATILDA 데이터셋에서 엣지 최대 95% 제거하면서 최적해 갭 1% 이내 유지
- 3.기하 구조 정보와 조합최적화 기술 결합으로 고정 휴리스틱 방식의 한계 극복
- 4.TSPLIB 대규모 인스턴스에서 가지치기율 99% 초과에도 갭 1% 미만 유지하는 일반화 입증
왜 중요한가?
대규모 TSP 정밀 해법의 병목인 그래프 크기를 인스턴스 구조에 맞춰 학습적으로 줄인다는 점에서, 물류·경로 최적화 등 실무 조합최적화의 계산 비용을 크게 낮출 수 있는 접근이다. 99% 가지치기에도 1% 미만 갭 유지는 고정 휴리스틱 대비 뚜렷한 개선이다.
언급 프로젝트
대규모 여행 외판원 문제(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
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 13:08AI 초안
