설명

아래 그림과 같이 연결된 8개의 원에 숫자 1부터 8까지 배치하세요.
한 가지 제한 사항: 서로 옆에 있는 두 개의 원에는 숫자가 있어야 합니다.
직렬이 아닌 할당된 것입니다.

                   1
                  /| \
                 2-3-4
                 |X|X|
                 5-6-7
                  \|/
                   8

대형 모델 유형 :MIP

카테고리 : 메가 슬롯 모델 라이브러리

메인 파일 : marilyn.gms

$title 숫자 퍼즐(MARILYN,SEQ=193)

$onText
아래 그림과 같이 연결된 8개의 원에 숫자 1부터 8까지를 배치합니다.
한 가지 제한 사항: 서로 옆에 있는 두 개의 원에는 숫자가 있어야 합니다.
직렬이 아닌 할당된 것입니다.

                   1
                  /| \
                 2-3-4
                 |X|X|
                 5-6-7
                  \|/
                   8

Savant, M, Ask Marilyn, 1988. 퍼레이드, 5월 23일

키워드: 혼합 정수 선형 계획법, 8자리 퍼즐
$offText

세트
   c '원' / c1*c8 /
   순(c,c) / c1.(c2,c3,c4)
                 c2.(c3,c5,c6)
                 c3.(c4,c5,c6,c7)
                 c4.(c6,c7)
                 c5.(c6,c8)
                 c6.(c7,c8)
                 c7.c8 /;

별칭(c,cc);

순(c,cc) = 순(c,cc) + 순(cc,c);

정수 변수 x(c) '원 안에 들어갈 숫자';

바이너리 변수
   ll(c,cc) '작거나 큰 표시기'
   y(c,cc) '숫자 할당';

가변 더미;

방정식
   less(c,c) '더 작은 이웃을 갖는 링크'
   more(c,cc) '더 큰 이웃을 갖는 링크'
   cross(c,cc) '링크는 한쪽 방향이거나 다른 쪽입니다.'
   digit(c) '원에 숫자 할당'
   rowsum(c) '할당 조건 1'
   colsum(c) '할당 조건 2'
   obj;

x.lo(c) = 1;
x.up(c) = 8;

* 이웃과의 거리가 최소 2 이상
* neighbor(net(c,cc))..abs(x(cc) - x(c)) =g= 2;
less(net(c,cc)).. x(cc) =l= x(c) - 2 + 9*ll(c,cc);

more(net(c,cc)).. x(cc) =g= x(c) + 2 - 9*ll(cc,c);

cross(net(c,cc)).. ll(c,cc) + ll(cc,c) =e= 1;

* 1,2,..8의 값을 x에 할당
* 숫자(c).. sum(cc, x(cc) = ord(c)) =e= 1;
숫자(c).. x(c) =e= sum(cc, ord(cc)*y(c,cc));

rowsum(c).. sum(cc, y(c,cc)) =e= 1;

colsum(c)..sum(cc, y(cc,c)) =e= 1;

obj..dummy =e= sum(c, x(c));

* 아래 obj는 일부 시스템에서 매우 느립니다.
* obj..dummy =e= sum(c, ord(c)*x(c));
모델 m / 모두 /;

* OSL에는 bbpreproc 사용
m을 풀어보세요. mip min dummy;