설명

라틴 사각형은 어떤 물체도 없도록 물체를 배열한 것입니다.
행이나 열에서 반복됩니다. 두 개의 라틴 정사각형은 직교합니다.
모든 항목이 다른 경우. 예를 들어,

        하나 둘
       1 3 2 2 1 3
       3 2 1 1 3 2
       2 1 3 3 2 1

n = 10인 경우는 역사적으로 중요한 의미가 있으며 1952년에야 해결되었습니다.

원래 공식이 올바르지 않습니다. 새로운 공식
올바른 솔루션을 생성하는 방법이 제시됩니다. 또한
용액 시간은 제형 세부 사항에 매우 민감하며 다음 사항에 따라 달라집니다.
사용되는 알고리즘의 종류.

선을 편집하여 사각형의 크기를 쉽게 변경할 수 있습니다.
행, 열 및 값의 정의를 포함합니다.
아래에 정의를 설정하세요. 이런 종류의 할당 문제는 매우
범용 MIP 코드의 경우 해결하기 어렵습니다.

대형 모델 유형 :MIP

카테고리 : 무료 슬롯 모델 라이브러리

메인 파일 : latin.gms

$title 직교 라틴-제곱 문제(LATIN,SEQ=159)

$onText
라틴방진은 어떤 물체도 없도록 물체를 배열한 것입니다.
행이나 열에서 반복됩니다. 두 개의 라틴 정사각형은 직교합니다.
모든 항목이 다른 경우. 예를 들어,

        하나 둘
       1 3 2 2 1 3
       3 2 1 1 3 2
       2 1 3 3 2 1

n = 10인 경우는 역사적으로 중요한 의미가 있으며 1952년에야 해결되었습니다.

원래 공식이 올바르지 않습니다. 새로운 공식
올바른 솔루션을 생성하는 방법이 제시됩니다. 또한
용액 시간은 제형 세부 사항에 매우 민감하며 다음 사항에 따라 달라집니다.
사용되는 알고리즘의 종류.

선을 편집하여 사각형의 크기를 쉽게 변경할 수 있습니다.
행, 열 및 값의 정의를 포함합니다.
아래에 정의를 설정하세요. 이런 종류의 할당 문제는 매우
범용 MIP 코드의 경우 해결하기 어렵습니다.

Dantzig, GB, 26.3장. 선형 프로그래밍 및 확장.
프린스턴 대학 출판부, 뉴저지주 프린스턴, 1963년.

키워드: 혼합 정수 선형 프로그래밍, 라틴 제곱, 수학
$offText

$eolCom //

$SIZE를 설정하지 않은 경우 $set SIZE 4 // 무료 슬롯 명령줄에서 --SIZE=n을 새 크기 n으로 설정

세트
   k '행' / row1*row%SIZE% /
   l '열' / col1*col%SIZE% /
   v '값' / val1*val%SIZE% /;

별칭(i,j,v);

$onText 원래 공식
사각형은 행 및 열 인덱스에 k,l을 사용합니다. 첫 번째
인덱스 위치(i)는 정사각형 1과 두 번째 값에 대한 것입니다.
인덱스 위치(j)는 정사각형 2에 대한 것입니다. 예를 들어, 셀 2,3
위에 표시된 라틴 사각형의 값은 다음과 같이 정의됩니다.
다음 인덱스 값 중 하나:

    x.fx('val1','val2','row2',col3') = 1;

원래 공식이 올바르지 않습니다. 예를 들어 다음을 선택할 수 있습니다.
임의의 셀(k,l)을 선택하고 셀 값을 동일하게 만들고
모델은 실현 가능한 솔루션을 찾을 것입니다. 예를 들어 다음과 같이 설정할 수 있습니다.

    x.fx('val1','val1','row1','col1') = 1;

그리고 실현 가능한 솔루션을 얻으세요. 오리지널 제형과 새로운 제형 모두
주어진다.
$offText

변수
   x(i,j,k,l) '셀(k,l)에 할당된 쌍 (i,j)'
   z '어떤 목적';

이진변수 x;

방정식
   c1(i,j) '각 셀에 대해 하나의 항목 쌍만 선택'
   c2(k,l) '항목 쌍은 한 번만 나타날 수 있습니다.'
   c3(i,l) '항목은 정사각형 1의 각 열에서 고유해야 합니다.'
   c4(j,l) '2번째 사각형의 항목은 각 열에서 고유해야 합니다.'
   c5(i,k) '1번째 항목은 각 행에서 고유해야 합니다.'
   c6(j,k) '2번째 사각형의 항목은 각 행에서 고유해야 합니다.'
   obj '일부 목적 함수';

c1(i,j)..sum((k,l), x(i,j,k,l)) =e= 1;

c2(k,l)..sum((i,j), x(i,j,k,l)) =e= 1;

c3(i,l)..sum((j,k), x(i,j,k,l)) =e= 1;

c4(j,l)..sum((i,k), x(i,j,k,l)) =e= 1;

c5(i,k)..sum((j,l), x(i,j,k,l)) =e= 1;

c6(j,k)..sum((i,l), x(i,j,k,l)) =e= 1;

obj.. z =e= sum((i,j,k,l), x(i,j,k,l));

라틴어 모델 / 모두 /;

매개변수 보고서(*,k,l);

옵션 보고서:0:1:1;

$onText는 이전 모델을 건너뜁니다.
* 잘못된 해결책을 강요하다
x.fx('val1','val1','row1','col1') = 1;

mip를 사용하여 라틴어 최소화 z를 해결합니다.

루프((i,j,k,l)$x.l(i,j,k,l),
   보고('하나',k,l) = ord(i);
   Report('two',k,l) = ord(j);
);
보고서 표시;
$offText

* 새로운 제제
s '사각형' / 하나, 둘 / 설정;

변수
   y(s,v,k,l) '사각형 s는 셀(k,l)에서 v 값을 갖습니다.'
   dev(v,k,l) '올바른 공식에서 벗어남'
   w '어떤 목적';

이진변수 y;

방정식
   n2(s,k,l) '각 셀에 대해 정확히 하나의 값'
   n3(s,v,l) '열 항목은 고유해야 합니다.'
   n5(s,v,k) '행 항목은 고유해야 합니다.'
   n6(v,k,l) '사각형의 항목은 달라야 합니다.'
   nobj '목적의 정의 - 무엇이든';

n2(s,k,l)..sum(v, y(s,v,k,l)) =e= 1;

n3(s,v,l)..sum(k, y(s,v,k,l)) =e= 1;

n5(s,v,k).. sum(l, y(s,v,k,l)) =e= 1;

n6(v,k,l).. 합계(s, y(s,v,k,l)) =l= 1;

nobj.. w =e= sum((s,v,k,l), y(s,v,k,l));

모델 newlatin / nobj, n2, n3, n5, n6 /;

* 솔루션 배치
y.fx('one','val1','row1','col1') = 1;

mip를 사용하여 newlatin min w를 해결합니다.

루프((s,v,k,l)$y.l(s,v,k,l),
   보고서(s,k,l) = ord(v);
   보고서(s,k,l) = ord(v);
);
보고서 표시;