설명
이것은 일련의 여행하는 세일즈맨의 네 번째 문제입니다.
문제. 여기서는 TSP1을 다시 살펴보고 더욱 스마트한 컷을 생성합니다.
첫 번째 완화는 TSP1과 동일합니다.
대형 모델 유형 :MIP
메인 파일 : tsp4.gms 포함: br17.inc
$title 여행하는 외판원 문제 - 4개(TSP4,SEQ=180)

$onText
이것은 여행하는 세일즈맨 시리즈의 네 번째 문제입니다.
문제. 여기서는 TSP1을 다시 살펴보고 더욱 스마트한 컷을 생성합니다.
첫 번째 이완은 TSP1과 동일합니다.

Kalvelagen, E, 무료 슬롯를 사용한 모델 구축. 곧

de Wetering, AV, 개인 통신.

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

$eolCom //

$include br17.inc

* 이 알고리즘의 경우 12개 도시로 구성된 더 큰 하위 집합을 시도할 수 있습니다.
i(ii) / i1*i12 /를 설정합니다.

* 옵션. MIP 솔버가 전역 최적값을 찾는지 확인하세요.
옵션 optCr = 0;

모델 할당/목적, rowsum, colsum/;

z를 최소화하는 mip를 사용하여 할당을 해결합니다.

* 투어 찾기 및 표시
t '투어' / t1*t17 /를 설정합니다.
abort$(card(t) < 카드(i)) "세트 t가 너무 작을 수 있습니다.";

세트
   투어(i,j,t) '하위 투어'
   Visited(i) '도시를 이미 방문했는지 여부를 표시합니다';

싱글톤 세트
   from(i) '항상 하나의 요소, 즉 from city를 포함합니다.'
   next(j) '항상 하나의 요소, 즉 to city를 포함합니다.'
   tt(t) '항상 하나의 요소, 즉 현재 하위 투어를 포함합니다.';

별칭(i,ix);

* 초기화
from(i)$(ord(i) = 1) = 예;    // 첫 번째 요소를 켭니다.
tt(t)$ (ord(t) = 1) = 예;    // 첫 번째 요소를 켭니다.

* 컷을 추가하여 하위 투어 제거
cc / c1*c1000 / 설정;

별칭(cc,ccc); // 최대 1000컷까지 허용

세트
   curcut(cc) '현재 컷은 항상 하나의 요소'
   allcuts(cc) '총 컷수';

매개변수
   컷코에프(cc, i, j)
   rhs(cc)
   nosubtours '하위 투어 수';

방정식 절단(cc) '동적 절단';

cut(allcuts).. sum((i,j), cutcoeff(allcuts,i,j)*x(i,j)) =l= rhs(allcuts);

모델 tspcut / 목표, rowsum, colsum, cut /;

curcut(cc)$(ord(cc) = 1) = 예;

스칼라 괜찮습니다.

루프(ccc,
* 초기화
   from(i)$(ord(i) = 1) = 예;    // 첫 번째 요소를 켭니다.
   tt(t)$( ord(t) = 1) = 예;    // 첫 번째 요소를 켭니다.
   투어(i,j,t) = 아니오;
   방문(i) = 아니오;
   루프(나,
      next(j)$(x.l(from,j) > 0.5) = 예;  // x.l(from,j) = 1인지 확인하면 위험합니다.
      투어(from,next,tt) = 예;           // 테이블에 저장
      방문(from) = 예;                // 'from' 도시를 방문한 것으로 표시
      from(j) = next(j);
      if(sum(visited(next),1) > 0, // 이미 방문한 경우...
         tt(t) = tt(t-1);
         loop(ix$(not Visited(ix)), // 새로운 하위 투어의 시작점을 찾습니다.
            (ix) = 예;
         );
      );
   );
   전시 투어;
   nosubtours = sum(t, max(0,smax(tour(i,j,t),1)));
   하위 투어를 표시하지 않습니다.

   break$(nosubtours = 1); // 완료: 하위 투어 없음

   // 컷 소개
   loop(t$(ord(t) <= nosubtours),
      rhs(커컷) = -1;
      루프(투어(i,j,t),
         cutcoeff(curcut, i, j)$(x.l(i,j) > 0.5) = 1;
* 할당 제약의 특성으로 인해 필요하지 않음
* cutcoeff(curcut, i, j)$(x.l(i,j) < 0.5) = -1;
         rhs(커컷) = rhs(커컷) + 1;
      );
      allcuts(curcut) = 예;   // 이 컷을 세트에 포함
      커컷(cc) = 커컷(cc-1);
   );
   z를 최소화하는 mip를 사용하여 tspcut을 해결합니다.
   tspcut.solPrint = %solPrint.quiet%;
   tspcut.limRow = 0;
   tspcut.limCol = 0;
);

디스플레이 x.l;
abort$(nosubtours <> 1) "컷이 너무 많이 필요합니다";