설명
이것은 일련의 여행하는 세일즈맨의 세 번째 문제입니다.
문제. 공식은 하위 투어 제거 기반을 사용합니다.
먼저 모든 하위 투어를 찾은 다음 적절한 항목을 추가하는 논리
제거 제약 조건.
소형 모델 유형 :MIP
메인 파일 : tsp3.gms 포함: br17.inc
$title 여행하는 외판원 문제 - 3개(TSP3,SEQ=179)

$onText
이것은 여행하는 세일즈맨 시리즈의 세 번째 문제입니다.
문제. 공식은 하위 투어 제거 기반을 사용합니다.
먼저 모든 하위 투어를 찾은 다음 적절한 항목을 추가하는 논리
제거 제약 조건.

Kalvelagen, E, 슬롯 나라를 사용한 모델 구축. 곧

de Wetering, AV, 개인 통신.

Lawler, EL, Lenstra, J K, Kan, A H G R 및 Shmoys, D B, Eds, The
여행하는 세일즈맨 문제, 조합 가이드 투어
최적화. 와일리, 1985.

추가 정보는 다음에서 확인할 수 있습니다.

/modlib/adddocs/tsp3doc.htm

키워드: 혼합 정수 선형 계획법, 여행하는 외판원 문제, 하위 여행
          제거
$offText

$eolCom //

$includebr17.inc

* 먼저 작은 하위 집합을 선택합니다.
i(ii) / i1*i6 /를 설정합니다.

$onText
이 코드는 까다롭고 모든 생성이
하위 집합은 아래 예를 통해 설명됩니다.

먼저 우리는 하나의 요소를 취합니다
   n1 예
   n2 아니요
그러면 i = i2에 대해 우리는
   n1 예 아니오
   n2 아니 아니 아니
   n3 예 예 n1의 사본에 i2를 추가=예
   n4 no tes n2의 복사본 + i2=yes 추가
그러면 i = i3에 대해 우리는
   n1 예 아니요 아니요
   n2 안돼 안돼 안돼
   n3 예 예 아니요
   n4 아니오 예 아니오
   n5 예 아니오 예
   n6 아니오 아니오 예
   n7 예 예 예
   n8 아니오 예 예
$offText

세트
   n 'subtour id' / n1*n500 / // 최대 1000개의 하위 집합
   si(n,i) '부분집합'
   sicomp(n,i) '하위 집합 보완'
   nn(n)
   nnn(n)
   커른(n);

* 트리 초기화
si('n1','i1') = 예;
si('n2','i1') = 아니요;
curn('n2') = 예;
nnn('n1') = 예;
nnn('n2') = 예;

루프(i$(ord(i) > 1),
   // 이전에 생성된 모든 세트의 복사본을 만듭니다.
   // 한 복사본에는 i가 포함되고 다른 복사본에는 포함되지 않습니다.
   nn(n) = nnn(n);
   루프(nn,
      커른(n) = 커른(n-1);
      nnn(커른) = 예;
      si(curn,j) = si(nn,j);  // 예전 것을 복사한다
      si(curn, i) = 예;
   );
);

sicomp(nnn,i) = si(nnn,i)가 아님;
si, sicop 표시;

$onText
다음과 같은 빈 행을 제외합니다.
       i1 i2 i3
   n2 안돼 안돼 안돼
그리고 "전체" 행은 다음과 같습니다:
       i1 i2 i3
   n7 예 예 예
$offText

n1(n) '간소화된 하위 투어 세트'를 설정합니다.

n1(nnn) = 예;
n1(nnn)$(sum(i$si(nnn,i),1) = 0) = 아니오;
n1(nnn)$(sum(i$si(nnn,i),1) = 카드(i)) = 아니오;

방정식
   se1(n) '하위 순회 제거 1'
   se2(n) '하위 순회 제거 2';

se1(n1).. sum(i$si(n1,i), sum(j$si(n1,j), x(i,j))) =l= sum(si(n1,i),1) - 1;

se2(n1).. sum(si(n1,i), sum(sicomp(n1,j), x(i,j))) =g= 1;

모델
   subt1 / 목표, rowsum, colsum, se1 /
   subt2 / 목표, rowsum, colsum, se2 /;

z를 최소화하는 mip를 사용하여 subt1을 해결합니다.
디스플레이 x.l

z를 최소화하는 mip를 사용하여 subt2를 해결합니다.
디스플레이 xl;