korea81998 계산

한국 술집 경로는 지금까지 해결된 TSP의 가장 큰 로드맵 사례입니다. 결코 쉬운 일은 아니었지만, TSP의 다른 네 가지 큰 사례를 해결하면서 얻은 경험에서 이익을 얻었습니다.

포인트 세트	해결 연도	B&B 크기	B&B CPU 시간	총 CPU 시간	경과 시간
49,603개의 미국 역사 유적지	2016	830,505	178.7 년	231 년	10 개월
49,687 영국 술집	2018	557,271	200.6 년	250 년	18 개월
57,912개의 네덜란드 기념물	2021	386,025	90.0 년	97 년	6 개월
40,426개의 일본 매장	2024	113,651	23.4 년	43 년	2 개월

표의 열에서 "B&B 크기"는 분기-한정 탐색 트리의 하위 문제 수를 나타내며, "B&B CPU 시간"은 탐색에 걸린 컴퓨터 시간(Linux 서버의 단일 프로세서 코어에서 실행하는 경우)을 나타내며, "총 CPU 시간"은 예제를 해결하는 데 걸린 총 시간(선형 프로그래밍 완화 구축 포함)의 대략적인 추정치를 나타내고, "경과 시간"은 계산 시작부터 끝까지 걸린 시간을 나타냅니다.

CPU 시간은 년 단위로 측정되며, 이 크기의 TSP 인스턴스를 해결하는 데 어려움이 있음을 분명히 보여줍니다. 이러한 예제에 대한 주요 계산은 워털루 대학교의 Linux 서버 네트워크에서 수행되었으며, 서버가 일상적인 프로젝트로 바쁘지 않을 때 최대 수백 개의 프로세서 코어를 사용할 수 있었습니다. 보고된 시간은 긴 계산에서 사용된 프로세서 코어에 대한 시간의 합계입니다.

이 표의 두드러진 특징은 분기 및 경계 검색 트리에서 엄청나게 많은 하위 문제가 있다는 것입니다. korea81998을 풀 기회를 갖기 위해 우리는 검색 크기를 줄이기 위해 최적화 전략을 조정해야 한다는 것을 알았습니다.

두 개의 2.10GHz Intel Xeon Gold 6238 CPU(각각 22개 코어)가 장착된 Linux 서버에서 44개 프로세서 코어를 사용하여 OSRM 소프트웨어는 1.5일 남짓 만에 korea81998 거리 표를 계산했습니다. 데이터를 간단히 확인한 후, 2024년 12월 10일에 TSPLIB 파일을 Keld Helsgaun에게 보냈습니다. Keld는 고품질 TSP 투어를 찾는 데 있어 세계 최고의 전문가입니다. 그는 LKH 코드를 만든 사람으로, 이 코드는 오랫동안 TSP 휴리스틱 검색 소프트웨어의 표준이었습니다.

Keld가 korea81998 파일을 받은 지 한 시간 후, 그는 길이가 15399990인 LKH 투어를 찾았다는 간단한 메모를 보냈습니다. 다음 날 Keld는 47개의 LKH 투어를 병합하여 길이가 15386177인 투어를 찾아 결과를 개선했습니다. 12월 14일까지 Keld는 LKH+MERGE의 세 가지 독립적인 실행에서 길이가 같은 15386177인 투어를 찾았습니다.

이는 2024년 11월에 해결된 40,426개 정류장 일본 TSP에서 우리가 경험한 것과 유사합니다. 그 경우, 켈드의 결과는 나중에 가능한 가장 짧은 투어로 증명되었습니다. 그래서 우리는 15386177이 최적 값에 매우 가깝다고 확신했습니다. 두 달 후에 우리는 LKH+MERGE 투어가 korea81998에 최적이라는 것을 확실히 알게 되었습니다.

최적성 증명을 생성하는 계산에서 우리는 표준 관행을 따랐고 가장 잘 알려진 투어 길이보다 1 더 큰 상한으로 분기 및 경계 검색을 시작하여 검색이 최적 솔루션을 재생성하도록 강제했습니다(실행 시 확인으로). 하지만 시작 부분에 강한 경계를 두는 것은 계산에 큰 도움이 되었습니다.

초기 경계는 여러 가지 방법으로 Concorde 코드를 안내합니다. 분기 및 경계 검색에서 하위 문제를 정리할 수 있도록 하고, 코드가 초기 경계보다 더 나은 투어에 있을 수 없는 에지를 제거할 수 있도록 하며, 절단 평면을 찾기 위해 더 빠르고 느린 루틴을 전환하기 위한 허용 오차를 설정합니다.

하지만 우리가 연구하는 가장 큰 사례의 경우 LKH 투어가 제공하는 가장 큰 도움은 인간의 결정 측면에 있습니다. 2,141개 정류장 대전 투어와 같이 규모가 작은 사례의 경우 기본 설정으로 콩코드 시작 버튼을 누르고 최적의 솔루션을 기다리면 됩니다. 이는 가장 큰 사례의 경우는 해당되지 않습니다. 여기서 우리는 솔루션 프로세스의 잠재적 개선 사항을 연구하기 위해 해결 가능성의 한계를 넓히고 있습니다. 여기서 우리는 즉석에서 조정하고, 절단 평면 방법과 분기 및 경계 검색 사이를 전환하고, 새로운 절단 평면 루틴을 실험하고, 분기 규칙을 테스트하는 등의 작업을 수행합니다. 이러한 선택은 우리가 계산하는 하한과 가장 잘 알려진 투어에서 제공하는 상한 사이의 차이에 크게 의존합니다.

투어가 가능한 가장 짧다는 것을 증명하는 핵심은 TSP 인스턴스에 대한 선형 프로그래밍(LP) 완화를 구성하는 것입니다. 즉, 모든 TSP 투어가 후보 솔루션이 되는 LP 모델입니다. 최적의 LP 값(또는 보다 일반적으로 모든 이중 LP 솔루션의 값)이 β인 경우 어떤 투어도 β보다 짧은 길이를 가질 수 없습니다. 즉, β는 TSP의 하한으로, 투어 길이에 대한 품질 보증을 수립할 수 있는 수단을 제공합니다.

TSP의 LP 모델은 모든 지점 간 연결에 0과 1 사이의 (아마도 분수) 값을 할당합니다. 지점 간 연결은 두 개의 정류장을 연결합니다. 이를 링크 또는 에지라고 합니다. 투어는 모든 링크에 0 또는 1이 할당된 LP 솔루션으로 표현할 수 있습니다. 값 1이 할당된 링크는 투어에 사용된 링크에 해당합니다. LP 제약 조건은 모든 투어 솔루션에서 충족되는 규칙입니다. 도수 방정식이라고 하는 기본 규칙은 모든 정류장에 대해 정류장을 만나는 링크의 값이 합산 2가 되어야 한다는 것입니다. 하위 투어 부등식이라고 하는 중요한 추가 규칙은 정류장 S의 하위 집합에 대해 한쪽 끝은 S에 있고 다른 쪽 끝은 S에 없는 링크의 값이 최소 2여야 한다는 것입니다.

모든 값이 0 또는 1이고 모든 차수 방정식과 하위 투어 부등식을 만족하는 LP 솔루션은 투어입니다. 훌륭하지만 LP 솔루션은 분수 값을 가질 수 있습니다. 여기서 절단 평면 방법의 어려운 작업이 시작됩니다. 이 프로세스는 점점 더 많은 규칙을 추가하여 하한 β를 늘리고 LP 솔루션이 모든 0-1 값에 더 가까워지도록 강제합니다.

1월과 2월에 우리는 LP 완화를 천천히 구축하면서 Concorde의 절단 평면 방법 구현을 사용하여 LP의 품질을 반복적으로 개선했습니다. 즉, 생성된 하한을 증가시켰습니다. 이전 4개의 로드맵 인스턴스와 비교했을 때, 우리는 절단 평면을 찾기 위해 더 긴 계산을 사용했습니다. 전략의 변경 사항은 다음과 같습니다.

• 우리는 현재 LP 완화에서 절단 평면의 구조를 수정하기 위해 Concorde의 "조임" 루틴을 반복적으로 사용했습니다.
• 우리는 더욱 강력한 형태의 타이트 루틴을 구현하기 위해 네트워크 흐름 기술을 채택했습니다.
• 우리는 혼합 정수 프로그래밍(MIP)을 사용하여 문제의 하위 영역에서 도미노 패리티 불평등을 구축했습니다.
• 우리는 무작위성을 광범위하게 활용하여 수백 개의 Concorde 인스턴스를 병렬로 실행하고 그 결과로 나오는 LP 완화를 결합했습니다.

분기 및 경계 탐색은 후보 투어 세트를 두 개의 작은 세트로 반복적으로 분할하여 하한의 값을 높이려고 시도합니다. 예를 들어, 두 정거장 사이의 링크를 선택하고 나머지 투어를 링크를 확실히 사용하는 투어와 링크를 확실히 사용하지 않는 투어로 분할할 수 있습니다. 따라서 단일 부모에서 두 개의 새 자식 하위 문제를 만듭니다. 각 자식에 절단 평면 방법을 적용하면 각 경우 부모가 제공한 LP 경계를 개선하여 전체 하한을 늘릴 수 있습니다. 그리고 각 하위 문제에서 분기하여 프로세스를 계속할 수 있습니다.

korea81998 계산에서 우리는 문제를 두 개의 자식 하위 문제로 분할하는 데 사용된 구조를 식별하기 위해 "임시 분기"라는 느리지만 신중한 기술을 채택했습니다. 분기를 만들어야 할 때마다 구조에 대한 16가지 선택을 평가하여 각 후보 자식 하위 문제 쌍에 대해 절단 평면 프로세스를 수행한 다음 분기 단계에 대한 최종 선택을 내렸습니다. 이 프로세스는 분기당 계산 시간 측면에서 비용이 많이 들지만 연구의 주요 대상인 더 작은 분기 및 경계 검색 트리를 생성하는 경향이 있습니다.

우리는 또한 임시 분기와 함께 각 하위 문제에 대한 tight 기법을 반복적으로 사용했습니다. 이전 계산과 비교했을 때, 이 선택은 검색 노드당 훨씬 더 많은 시간이 필요했지만, 개선된 LP 경계는 다시 검색 트리의 크기를 줄이는 데 도움이 될 수 있습니다.

계산 결과는 다음 표에 요약되어 있습니다.

포인트 세트	해결 연도	B&B 크기	B&B CPU 시간	총 CPU 시간	경과 시간
81,998개의 한국 술집	2025	2,121	10.2 년	44 년	3 개월

물론 우리는 작은 검색 트리를 보고 그렇게 큰 TSP 인스턴스를 해결하게 되어 매우 기뻤습니다. 하지만 우리가 사용한 방법이 이 특정 사례에서 그저 운이 좋았을 뿐인지에 대한 자연스러운 의문이 제기됩니다. 이는 대규모의 시간 소모적인 계산 작업에서 발생하는 어려움으로, 대체 기술을 평가하기에 충분한 수의 시도를 할 리소스가 없습니다. 반면에 훨씬 더 큰 사례를 살펴볼 이유가 생깁니다. Excelsior!

투어 지도 도면은 모바일 친화적인 대화형 지도를 위한 오픈소스 JavaScript 라이브러리인 Leaflet을 사용하여 제작되었으며, OpenStreetMap, Carto Basemaps, Stadia Maps에서 만든 지도 타일을 활용했습니다.