설명
N개의 공이 주어지는데 그 중 n1은 색상 1이고 n2는 색상 2입니다... nk는 색상 k입니다. N개의 공을 N개의 순서로 할당하는 방법을 찾으세요. 한 가지 색상의 공이 같은 간격으로 균등하게 배치되도록 하는 슬롯 가능합니다. Bollapragada, Bussieck 및 Mallik의 논문에는 25가지 사례가 나열되어 있습니다. 사용 n번째 예를 선택하려면 명령줄 옵션 --curid n을 선택하세요. --curid가 다음과 같은 경우 누락되어 크레이지 슬롯 번호 12를 선택합니다. --sparse 1 옵션을 추가하면 다음과 같은 희소 흐름 그래프가 생성됩니다. 대략적인 해결책만 도출됩니다. 이 크레이지 슬롯에 대한 자세한 내용은 /team/mbussieck/isci/에서 확인할 수 있습니다.
대형 모델 유형 :MIP
카테고리 : 크레이지 슬롯 모델 라이브러리
메인 파일 : 크레이지 슬롯gms
$title ISCI 회전자 문제의 흐름 공식화(크레이지 슬롯SEQ=247)
$onText
N개의 공 중 n1은 색상 1이고, n2는 색상 2입니다.
nk는 색상 k입니다. N개의 공을 N개의 순서로 할당하는 방법을 찾으세요.
한 가지 색상의 공이 같은 간격으로 균등하게 배치되도록 하는 슬롯
가능합니다.
Bollapragada, Bussieck 및 Mallik의 논문에는 25가지 사례가 나열되어 있습니다. 사용
n번째 예를 선택하려면 명령줄 옵션 --curid n을 선택하세요. --curid가 다음과 같은 경우
누락되어 문제 번호 12를 선택합니다.
--sparse 1 옵션을 추가하면 다음과 같은 희소 흐름 그래프가 생성됩니다.
대략적인 해결책만 도출됩니다.
이 문제에 대한 자세한 내용은 /team/mbussieck/isci/에서 확인할 수 있습니다.
Bollapragada, S, Bussieck, M.R. 및 Mallik, S, 상업 예약
방송 텔레비전의 비디오테이프. 운영 연구, 2003
Bollapragada, S, Cheng, H, Phillips, M 및 Garbiras, M,
NBC의 최적화 시스템은 수익과 생산성을 높입니다.
인터페이스 31, 1(2002).
키워드: 혼합 정수 선형 계획법, 할당 문제, 스케줄링
상업용 비디오테이프, 텔레비전 방송
$offText
$curid를 설정하지 않은 경우 $set curid 12
세트
sp '슬롯 + 초기' / 0*100 /
s(sp) '슬롯'
c '색상' / R '빨간색', B '파란색', W '흰색', G '녹색', Y '노란색' /
id '테스트 세트 ID' / 1*25 /;
테이블 idc(id,c) '색상 수'
R B W G Y
1 5 3
2 4 2 2
3 5 3 2
4 6 3 2
5 6 4 2
6 4 3 3 2
7 6 4 4
8 6 5 4
9 8 3 3 2
10 7 6 4
11 8 7 5
12 8 7 3 2
13 5 5 5 4 1
14 8 6 6 5
15 7 6 5 4 3
16 10 8 7 5
17 9 7 6 5 3
18 17 10 8 5
19 16 15 14
20 25 13 12
21 21 16 13
22 26 12 10 2
23 25 23 12
24 27 25 14 9
25 33 25 21 15 6;
Preplace(id,sp,c) 'preplaced ball' 설정
/ 1. (6.B, 8.R)
2. (1.R, 2.B, 3.W)
3. (1.B, 2.W)
4. (1.B, 5.W, 6.B)
5. (1.R, 3.B)
6. (2.R, 3.R, 4.B, 6.W)
7. (1.R, 6.B, 14.W)
8. (1.B, 4.W, 7.R)
9. (1.R, 3.W, 5.G)
10. (1.B, 2.B, 15.W)
11. (1.W, 5.R, 10.B)
12. (1.W, 5.R, 10.B, 20.G)
13. (2.R, 10.R, 17.B)
14. (1.R, 6.G, 25.W)
15. (1.R, 5.R, 6.G, 25.W)
16. (3.R, 9.G, 15.B)
17. (3.R, 9.G, 15.B)
18. (1.W, 9.G, 17.R, 38.R)
19. (1.B, 5.B, 6.W)
20. (7.R, 15.B, 17.B, 20.W, 39.W)
21. (7.R, 15.B, 17.B, 20.W, 39.W)
22. (1.B, 9.R, 10.G, 20.R)
23. (1.W, 17.R, 30.B)
24. (1.R, 5.B, 11.G, 15.B, 25.G)
25. (1.B, 5.G, 6.R, 25.W, 41.Y) /;
매개변수 nc(c) '색상 수';
nc(c) = idc('%curid%',c);
스칼라 n '광고 수';
n = 합(c,nc(c));
매개변수 dc(c) '이상적인 거리';
dc(c)$nc(c) = n/nc(c);
별칭(sp,i,j);
s(sp+1) = ord(sp) <= n;
* 네트워크 구축
Set net(c,i,j) '네트워크 연결 슬롯';
매개변수 dev(c,i,j) '이상적인 거리에 대한 거리 i와 j의 편차';
스칼라
isf '초기 범위 인자' / 2 /
msf '중간 범위 인자 범위' / 0.1 /
sf '스팬 팩터';
$if sparse로 설정됨 $goTo dosparse
* 조밀한 그래프
루프(c$nc(c),
루프(i$(ord(i) <= n+1),
net(c,i,j)$(ord(j) > ord(i)) = 예;
);
);
$label dosparse
루프(c$nc(c),
net(c,'0',j)$(ord(j) > 1 및 ord(j) <= min(n+1,1+isf*dc(c))) = 예;
sf = msf;
if(sf*dc(c) < 5, sf = 5/dc(c));
loop(i$(ord(i) > 1 및 ord(i) <= n+1),
net(c,i,j)$(ord(j) > max(ord(i),ord(i)+(1-sf)*dc(c)) 및
ord(j) <= min(n+1,ord(i)+(1+sf)*dc(c))) = 예;
);
);
* 호는 소스로 돌아갑니다.
net(c,s,'0') = 예;
dev(net(c,i,j))$(ord(i) > 1 및 ord(j) > 1) = abs(ord(j) - ord(i) - dc(c));
* 옵션 dev:5:0:1; 디스플레이 개발;
* 모델
변수
f(c,i,j) '흐름 변수'
p(c,i) '배치 변수'
obj '객관변수';
이진변수 p;
양의 변수 f;
방정식
bal(c,i) '흐름 균형 방정식'
balinit(c) '노드 0의 흐름 균형'
defopen(c,i) '다른 색상의 슬롯을 닫습니다'
defsump(c) '열린 슬롯 수'
covslot(i) '슬롯 덮개 요구 사항'
defobj '목적 함수';
bal(c,s)$nc(c).. sum(net(c,j,s), f(net)) - sum(net(c,s,j), f(net)) =e= 0;
balinit(c)$nc(c).. sum(net(c,'0',j), f(net)) =e= 1;
defopen(c,s)$nc(c).. sum(net(c,s,j), f(net)) =e= p(c,s);
defsump(c)$nc(c).. sum(s, p(c,s)) =e= nc(c);
covslot(s).. sum(c$nc(c), p(c,s)) =e= 1;
defobj..obj =e= sum(net, dev(net)*f(net));
모델 광고/모두/;
옵션 optCr = 0, resLim = 300;
sol '솔루션 보고 세트'를 설정합니다.
매개변수 solrep;
* 우선순위를 시도해 보세요
commercial.priorOpt = 1;
p.prior(c,s) = nc(c);
* 미리 배치된 모델을 먼저 해결하세요.
p.lo(c,s)$preplace('%curid%',s,c) = 1;
mip를 사용하여 상업용 min obj를 해결합니다.
sol('%curid%','PRE',s,c) = p.l(c,s);
solrep('PRE','obj') = obj.l;
solrep('PRE','bnd') = commercial.objEst;
solrep('PRE','res') = commercial.resUsd;
* 미리 배치된 공을 놓습니다.
p.lo(c,s)$preplace('%curid%',s,c) = 0;
* CPLEX를 사용하는 경우 사전 수정된 솔루션부터 시작하겠습니다.
* (다음 세 줄의 주석 처리 해제)
* 파일 fcpx / cplex.opt /;
* putClose fcpx 'mipStart 1';
* 상업.opt파일 = 1;
mip를 사용하여 상업용 min obj를 해결합니다.
sol('%curid%','FREE',s,c) = p.l(c,s);
solrep('FREE','obj') = obj.l;
solrep('FREE','bnd') = commercial.objEst;
solrep('FREE','res') = commercial.resUsd;
디스플레이 솔, 솔렙;
* 배치런에 유용한 시간, objs, bnd가 포함된 보고서를 원하시면,
* $exit 주석 해제
$exit
파일 fsol / allsol.txt /;
* 솔루션 파일에 추가하지만 첫 번째 파일에는 추가하지 않음
fsol.ap$(not sameas('%curid%','1')) = 1;
put fsol '%curid% 인스턴스에 대한 솔루션: obj_pre: ' solrep('PRE','obj'):12:5
' obj_free: ' solrep('FREE','obj'):12:5 /
'슬롯 프리프리' /;
루프(s(sp),
넣어 (ord(sp)-1):3:0 ' '
loop(c$sol('%curid%','PRE' ,s,c), put c.tl:1 ' ';);
loop(c$sol('%curid%','FREE',s,c), put c.tl:1 /;);
);
파일 ftim / alltim.txt /;
* 시간 파일에 추가하지만 첫 번째 파일에는 추가하지 않음
ftim.ap$(not sameas('%curid%','1')) = 1;
* 첫 번째 헤더에 헤더를 넣습니다.
put$sameas('%curid%','1') ftim
' 미리 배치된 공이 없는 공 배치' /
'id obj bnd res obj bnd res'/;
put ftim (%curid%):2:0 solrep('PRE','obj'):12:5
solrep('PRE','bnd'):12:5
solrep('PRE','res'):12:5
solrep('무료','obj'):12:5
solrep('무료','bnd'):12:5
solrep('FREE','res'):12:5 /;