설명

이것은 원래 COEX 문제보다 더 엄격한 공식입니다.
우리는 보드의 크기를 5로 설정했습니다.
신속하게 솔루션을 제공합니다. 게다가 우리는 한 명의 여왕의 위치를 ​​고정합니다.

두 여왕의 군대(흑백)가 평화롭게 공존하고 있습니다.
체스판이 다음과 같은 방식으로 보드 위에 배치되었을 때
서로 반대되는 군대의 두 여왕은 서로를 공격할 수 없습니다. 는
문제는 크기가 같은 최대 2개의 군대를 찾는 것입니다.

대형 모델 유형 :MIP

카테고리 : 슬롯 머신 모델 라이브러리

메인 파일 : coexx.gms

$title 평화롭게 공존하는 여왕의 군대 - 긴밀함 (COEXX,SEQ=218)

$onText
이는 원래 COEX 문제보다 더 엄격한 공식입니다.
우리는 보드의 크기를 5로 설정했습니다.
신속하게 솔루션을 제공합니다. 게다가 우리는 한 명의 여왕의 위치를 ​​고정합니다.

두 여왕의 군대(흑백)가 평화롭게 공존하고 있습니다.
체스판이 다음과 같은 방식으로 보드 위에 배치되었을 때
서로 반대되는 군대의 두 여왕은 서로를 공격할 수 없습니다. 는
문제는 크기가 같은 최대 2개의 군대를 찾는 것입니다.

보쉬, R, 마인드 샤프너. OPTIMA MPS 뉴스레터(2000).

키워드: 혼합 정수 선형 계획법, 수학 게임, 조합 최적화,
          평화롭게 공존하는 여왕의 군대
$offText

$eolCom //

세트
   i '체스판 크기' / 1*5 / // 체스에는 8을 사용합니다(13).
   s '대각선 오프셋' / 1*7 /;   // 2i-3 대각선

스칼라 표현은 's의 올바른 크기'입니다.
idiags = 2*카드(i) - 3;
abort$(카드 <> idiags)의 크기가 잘못되었습니다.', idiags;

별칭(i,j);

매개변수
   sh(s) '대각선 이동 값'
   rev(s,i) '역방향 이동 순서';

sh(s) = ord(s) - 카드(i) + 1 ;
rev(s,i) = 카드(i) + 1 - 2*ord(i) + sh(s);

바이너리 변수
   xw(i,j) '하얀 여왕이 있습니다'
   xb(i,j) '검은 여왕이 있습니다'
   wa(i) '행에 흰색 i'
   wb(i) 'j열의 흰색'
   wc(s) '대각선 안의 흰색'
   wd(s) '뒤쪽 대각선 s의 흰색';

가변 tot;

방정식
   aw(i,j) '행 i에 흰색'
   bw(j,i) 'j열의 흰색'
   cw(s,i) '대각선 s의 흰색'
   dw(s,i) '뒤쪽 대각선 s의 흰색'
   으아 '토탈 화이트'
   ab(i,j) '행 i의 검은색'
   bb(j,i) 'j열에 검정색'
   cb(s,i) '대각선 s의 검정색'
   db(s,i) '뒤쪽 대각선 s의 검정색'
   eb '완전 검은색';

aw(i,j)..wa(i) =g= xw(i,j);

bw(j,i)..wb(j) =g= xw(i,j);

cw(s,i).. wc(s) =g= xw(i, i + sh(s));

dw(s,i)..wd(s) =g= xw(i,i + rev(s,i));

ab(i,j).. 1 - wa(i) =g= xb(i,j);

bb(j,i).. 1 - wb(j) =g= xb(i,j);

cb(s,i).. 1 - wc(s) =g= xb(i, i + sh(s));

db(s,i).. 1 - wd(s) =g= xb(i, i + rev(s,i));

eb.. tot =e= sum((i,j), xb(i,j));

ew.. tot =e= sum((i,j), xw(i,j));

모델군 / 모두 /;

옵션 limCol = 0, limRow = 0;

xb.fx('1','1') = 1; // NW 코너의 한 위치를 고정합니다.

밉을 사용하여 군대를 최대화하는 문제를 해결합니다.