설명

오두막이나 마을은 10 x 10 격자의 20개 위치에 있습니다. 문제
구호 패키지를 위한 가장 좋은 두 곳의 드롭 위치를 찾는 것입니다.
마을 사람들의 이동 거리가 최소화됩니다.

우리는 이 문제를 공장 위치 문제로 보고 효율성을 추적합니다.
여러 방울의 경계. 두 방울에 대한 최적의 솔루션은 D.8과 E.2입니다.

또 다른 흥미로운 질문은 다음과 같습니다. 다른 드롭 위치가 몇 개나 있습니까?
예를 들어 가장 좋은 위치의 3%로 이동한 총 거리가 있습니다.

대형 모델 유형 :MIP

메인 파일 : relief.gms

$title 구호 임무 (RELIEF,SEQ=353)

$onText
오두막이나 마을은 10 x 10 그리드의 20개 위치에 있습니다. 문제
구호 패키지를 위한 가장 좋은 두 곳의 드롭 위치를 찾는 것입니다.
마을 사람들의 이동 거리가 최소화됩니다.

우리는 이 문제를 공장 위치 문제로 보고 효율성을 추적합니다.
여러 방울의 경계. 두 방울에 대한 최적의 솔루션은 D.8과 E.2입니다.

또 다른 흥미로운 질문은 다음과 같습니다. 다른 드롭 위치가 몇 개나 있습니까?
예를 들어 가장 좋은 위치의 3%로 이동한 총 거리가 있습니다.

Toczek J, 구호 임무, ORMS Today 37, 4(2010), 14페이지

키워드: 혼합 정수 선형 계획법, 공장 위치 문제, 조정 완화
$offText

$eolCom //

세트
   r '행' / A*J /
   c '열' / 1*10 /
   d '방울' / d1*d20 /;

표 dem(r,c) '구제 요구'
       1 2 3 4 5 6 7 8 9 10
   A 1
   비 1 1 1
   씨 1 1 1 1 1
   디 1 1 1
   전자 1 1
   F 1
   지 1
   H 1 1
   나
   J 1 1;

별칭 (r,rr), (c,cc);

Huts(r,c) '산장 위치'를 설정합니다.

매개변수
   dis(r,c,r,c) '유클리드 거리'
   numdrops '방울 수'
   maxdem '최대 드롭 요구량';

오두막(r,c) = dem(r,c);
maxdem = sum(huts, dem(huts));
dis(huts(r,c),rr,cc) = edist(r.pos-rr.pos,c.pos-cc.pos);

변수
   drop(r,c) '드롭 위치'
   walk(r,c,r,c) '산장에서 가장 가까운 낙하 지점까지 걸어간 거리'
   총 '걸은 총 거리';

바이너리 변수 드롭;
양수 가변 걷기;

방정식 수요, 공급, 적자, defnumdrop;

수요(오두막).. sum((r,c), walk(오두막,r,c)) =e= 1;

공급(r,c).. sum(huts, walk(huts,r,c)) =l= drop(r,c)*maxdem;

deftotal.. total =e= sum((huts,r,c), dis(huts,r,c)*walk(huts,r,c));

defnumdrop.. sum((r,c), drop(r,c)) =e= numdrops;

모델 m / 모두 /;

* -------------
* 최고의 2방울 솔루션을 얻으세요
* -------------
숫자 = 2;
옵션 limRow = 0, limCol = 0, optCr = 0,solvLink = 2, resLim = 60;
m.solPrint = 0;

mip를 사용하여 m min 총계를 해결합니다.

디스플레이 drop.l;

* -----------
* 효율적인 경계선 추적
* -----------
매개변수 QDrep '신속하고 더러운 보고서';

루프(d,
   numdrops = d.pos;
   mip를 사용하여 m min 총계를 해결합니다.
   m.solPrint = 2;
   // MIP 코드(CPLEX)가 분수 값을 반환할 수 있으므로 round()를 사용합니다.
   QDrep(r,c,d)$round(drop.l(r,c)) = sum ( 오두막, dis(huts,r,c)*walk.l(huts,r,c)) + eps*huts(r,c)*drop.l(r,c);
   QDrep('max','dist',d) = smax((huts,r,c), dis(huts,r,c)*walk.l(huts,r,c));
   QDrep('tot','dist',d) = sum ((huts,r,c), dis(huts,r,c)*walk.l(huts,r,c));
   QDrep('CPU','used',d) = m.resUsd;
);

QDrep을 표시합니다.

* ----------------------------------------------------------------
* 두 개의 드롭 포인트에 대해 최고 x% 이내의 모든 드롭 포인트를 찾습니다.
*
* n번째 정수 해를 제외하려면 다음과 같이 작성할 수 있습니다.
* cut(n).. sum(i, abs(x(i) - xsol(i,n)) =g= 1;
* abs()를 시뮬레이션하면 다음과 같은 결과가 나옵니다.
* cut(n).. sum((r,c), cutval(n,r,c)*drop(r,c)) =l= 1;
* cutval()에는 제외할 솔루션이 포함되어 있습니다.
* ----------------------------------------------------------------

세트
   nn '닫힌 해의 최대 개수' / n1*n50 /
   n(nn) '동적 집합';

매개변수
   '드롭 포인트의 총 거리' 제한
   objval(nn) '총 이동 마일'
   cutval(nn,r,c) '컷 생성을 위한 모든 가능한 솔루션';

숫자 = 2;
mip를 사용하여 m min 총계를 해결합니다.
한계 = 1.03*total.l;

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

cut(n).. sum((r,c), cutval(n,r,c)*drop(r,c)) =l= 1;

모델 mm / m, 컷 /;

n(nn) = 아니오;  // 컷 세트 지우기

mm.solveStat = %solveStat.normalCompletion%;
mm.modelStat = %modelStat.optimal%;
mm.solPrint = 0;

loop(nn$(mm.solveStat = %solveStat.normalCompletion% 및
         mm.modelStat = %modelStat.optimal% 및
         total.l < 제한),
   n(nn) = 예;   //설정할 요소 추가
   cutval(nn,r,c) = round(drop.l(r,c));
   mip를 사용하여 mm min total을 해결합니다.
   mm.solPrint = 0;
   objval(nn) = total.l;
);

옵션 컷발:0:1:1;
표시 objval, cutval;

매개변수 적중;
hit(r,c) = sum(nn, cutval(nn,r,c));
조회수 표시;