0
나는 GLPK와 함께 제공된 travelling salesman example으로 놀고 있는데, 합리적으로 해결할 것으로 예상되는 문제 크기에 대한 느낌을 얻으려고합니다. 나는 50 개의 노드 그래프를 해결할 수 있었지만, 100 개의 노드는 합리적인 시간대 (현대 하드웨어에서는 30 분 정도)에 수렴하지 않는 것 같습니다.GLPK로 어떤 크기의 투어를 할 수 있습니까?
GLPK에는 MIP 해석기에 대한 다양한 옵션이 있습니다. 다양한 조합을 시도했지만 어떤 옵션이 도움이 될지 명확하지 않습니다. This page has some discussion 다소 오래되어 조언이 다소 일반적입니다.
실용적인 기간 (예 : 4 시간 미만)에서 GLPK가 100 노드 이상을 해결할 것으로 예상하는 것이 합리적입니까? 문제의 크기는 언제 다루기 힘들 수 있습니까? many command-line options 중 어떤 것이 도움이 될까요?
아, 모든 가능한 휴리스틱뿐만 아니라 복잡성에 대해서도 알고 있습니다. 필자는 Python에서 간단한 발견 방법을 구현하여 최대 수천 개의 도시를 해결할 수 있습니다. 내 질문은 순수 LP + MIP 해석기 인 GLPK가 합리적인 크기의 (유클리드) TSP를 풀 것으로 예상 할 수 있는지 여부입니다. 필자의 테스트에서는 혼합 정수 솔버가 수렴하는데 아주 오랜 시간이 걸리는 것으로 보인다. 필자는 특히 명령 줄 옵션을 사용하여이 측면을 개선 할 수 있는지 여부를 궁금해합니다. 아니면 제가 잘못한 예를 제가 연계 한 것입니까? –
@ire_and_curses이 측면에서 GLPK를 향상시키는 방법을 보려면 tspsol 및 glptsp.c 코드를 참조하십시오. 마지막으로 "순수 LP + MIP"솔버가 TSP에 가장 적합한 방법으로 호출됩니다. – Ali
+1 : 당신의 대답은 도움이됩니다. 나는 tspsol에 대한 코드를 살펴 봤다. 이 문제는 GLPK 저자가 작성한 것으로 솔버만으로는이 문제에 대해 큰 진전을 이루지 못한다는 증거를 얻을 수 있습니다. 또한 이것이 사용자 지정 솔루션이 아닌 예제라는 점도 유의하십시오. 기본 분기와 경계를 사용합니다.맨 위에있는 주석을보십시오 : *이 프로그램은 단지 예시 일뿐입니다. 최첨단 코드가 아니므로이 코드를 사용하여 TSP 인스턴스가 작은 도시 (아마도 100 개가 넘지 않는 도시) 만 해결할 수 있습니다. * –