설명

이 MIP 모델은 기사의 최대 수를 찾습니다.
보드 위에 올려 놓았습니다. 두 가지 다른 제형이 제시됩니다.
두 번째 공식은 '단단'하며 특정 조건에서 더 나은 성능을 발휘할 수 있습니다.
MIP 코드. 최대 기사 수를 찾으면 일련의 문제를 해결합니다.
모든 솔루션을 찾기 위한 MIP.

허용되는 이동을 설명하기 위해 시차(상대 위치)를 사용합니다.
H와 V 라벨은 그림과 같이 수평 및 수직 이동을 나타냅니다.
아래:

                 0 0
                0 0
                  X
                0 0
                 0 0

대형 모델 유형 :MIP

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

메인 파일 : knights.gms

$title 최대 기사 수 문제(KNIGHTS,SEQ=158)

$onText
이 MIP 모델은 가능한 최대 기사 수를 찾습니다.
보드 위에 올려 놓았습니다. 두 가지 다른 제형이 제시됩니다.
두 번째 공식은 '단단'하며 특정 조건에서 더 나은 성능을 발휘할 수 있습니다.
MIP 코드. 최대 기사 수를 찾으면 일련의 문제를 해결합니다.
모든 솔루션을 찾기 위한 MIP.

허용되는 이동을 설명하기 위해 시차(상대 위치)를 사용합니다.
H와 V 라벨은 그림과 같이 수평 및 수직 이동을 나타냅니다.
아래:

                 0 0
                0 0
                  X
                0 0
                 0 0

Dudeney, HE, 수학의 오락. 1970년 뉴욕 도버.

키워드: 혼합 정수 선형 계획법, 최대 기사 문제, 수학
$offText

세트
   i '보드 크기' / 1*8 /
   n '가능한 이동 횟수' / m1*m8 /;

별칭(i,j,k);

Table move(*,n) '가능한 모든 기사 이동'
      m1 m2 m3 m4 m5 m6 m7 m8
   H -2 -2 -1 -1 +1 +1 +2 +2
   V -1 +1 -2 +2 -2 +2 -1 +1;

가변 합계;

이진변수 x(i,j);

방정식
   deftotal '탑승한 총 기사 수'
   defmove(i,j) '이동 제한'
   defmovex(n,i,j) '이동 제한';

deftotal.. total =e= sum((i,j), x(i,j));

defmove(i,j).. sum(n, x(i + move('h',n),j + move('v',n))) =l= 카드(i)*(1 - x(i,j));

defmovex(n,i,j).. x(i + move('h',n),j + move('v',n)) =l= 1 - x(i,j);

모델
   기사 / deftotal, defmove /
   Knightx / deftotal, defmovex /;

옵션 optCr = 0, optCa = .999;

mip max total을 사용하여 기사를 해결합니다.
mip max total을 사용하여 Knightx를 해결합니다.

* 이제 우리는 정렬할 수 있는 방법이 얼마나 많은지 알아보겠습니다.
* 같은 수의 기사.

스칼라 맥스나이트;
maxknight = total.l;
total.lo = total.l - 0.5;

옵션 optCr = 1, optCa = 100, limCol = 0, limRow = 0, solPrint = off;

세트
   ss '최대 솔루션 그룹 수' / seq1*seq20 /
   s(ss) '솔루션 그룹에 대한 동적 세트';

매개변수 cutval '컷 생성을 위한 가능한 모든 솔루션';

방정식 cut(ss) '제거할 알려진 솔루션';

cut(s).. sum((i,j), cutval(s,i,j)*x(i,j)) =l= maxknight - 1;

모델 나이트1 / deftotal, defmovex, cut /;

s(ss) = 아니오;
total.lo = maxknight - .5;
Knight1.solveStat = %solveStat.normalCompletion%;
Knight1.modelStat = %modelStat.optimal%;

loop(ss$(knight1.solveStat = %solveStat.normalCompletion% 및
        (knight1.modelStat = %modelStat.optimal% 또는
         Knight1.modelStat = %modelStat.integerSolution%)),
   s(ss) = 예;
   cutval(ss,i,j) = x.l(i,j);
   mip를 사용하여 총계를 최대화하는 Knight1을 해결합니다.
);

옵션 컷발:0:0:1;
컷발 표시;