설명

흰색과 검은색 공은 1 대 1의 큐브로 배열되어야 합니다.
볼이 있는 라인의 수를 최소화하는 방식으로 셀
동일한 색상입니다. 이 예에서는 큐브의 길이가 3입니다.
3x3x3의 큐브에는 총 49개의 선이 존재합니다. 변경하면 27줄
단 하나의 좌표, 평면 내 대각선 18개, 대각선 4개
비행기를 가로질러 가는 중입니다.

소형 모델 유형 :MIP

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

메인 파일 : cube.gms

$title 3차원 삼차원 십자가(CUBE,SEQ=42)

$onText
흰색 공과 검정색 공을 큐브 모양으로 배열합니다.
볼이 있는 라인의 수를 최소화하는 방식으로 셀
동일한 색상입니다. 이 예에서는 큐브의 길이가 3입니다.
3x3x3의 큐브에는 총 49개의 선이 존재합니다. 변경하면 27줄
단 하나의 좌표, 평면 내 대각선 18개, 대각선 4개
비행기를 타고 이동합니다.

Williams, H P, 정수 프로그래밍 공식화 실험
문제. 수학적 프로그래밍 연구 2(1974).

키워드: 혼합 정수 선형 계획법, 수학, 수학 게임,
          삼목, 틱택토
$offText

세트
   s '라인 식별을 위한 도메인' / a, b, c, incr, decr /
   x(s) '좌표 라벨' / a, b, c /
   d(s) '방향' / 증가, 감소 /
   b '경계' / 낮음, 높음 /;

별칭 (x,y,z), (d,dp), (s,sp,spp);

ld(s,sp,spp) '라인 정의'를 설정합니다.
ld("incr",y,z) = 예;
ld(x,"incr",z) = 예;
ld(x,y,"incr") = 예;
ld("incr",d,z) = 예;
ld(x,"incr",d) = 예;
ld(d,y,"incr") = 예;
ld("incr",d,dp) = 예;

디스플레이 ld;

매개변수
   ls(b) '선 정의에 대한 부호' / 낮음 1, 높음 -1 /
   lr(b) '라인 정의를 위한 rhs' / 낮음 2, 높음 -1 /
   df(x,s) '선 정의 함수';

df(x,y) = ord(y) - ord(x);
df(x,"decr") = 1 + 카드(x) - 2*ord(x);
디스플레이 df;

변수
   core(x,y,z) '공 배치(흰색 0 검정색 1)'
   line(s,sp,spp) '라인 식별'
   num '동일한 색상의 줄 수';

바이너리 가변 코어;
양수 변수 라인;

방정식
   nbb '총 공 정의 수'
   ldef(s,sp,spp,b) '라인 정의'
   ndef '줄 수 정의';

nbb.. sum((x,y,z), core(x,y,z)) =e= 바닥(카드(x)**3/2);

ldef(s,sp,spp,b)$ld(s,sp,spp)..
   ls(b)*sum(x, 코어(x+df(x,s),x+df(x,sp),x+df(x,spp))) =l= 라인(s,sp,spp) + lr(b);

ndef..num =e= sum((s,sp,spp)$ld(s,sp,spp), line(s,sp,spp));

모델 큐브 / 모두 /;

$if set nosolve $exit

* 참고: 솔버 성능이 크게 향상되어 optCa = 3.9가 제거되었습니다.
mip를 사용하여 숫자를 최소화하는 큐브를 해결합니다.