설명

이 예는 잘 알려진 Dantzig Wolfe 분해 방법을 구현합니다. 이
방법은 계수 행렬이 있는 선형 계획의 구조를 활용합니다.
특별한 형태를 가지고 있습니다:

     B0 B1 B2 ... Bk
         A1
             A2
                .
                 .  아크

특정 모델은 Ak가 발생하는 다중 상품 네트워크 흐름 문제입니다.
상품 흐름에 해당하고 Bk는 아크 용량을 나타냅니다.

대형 모델 유형 :LP

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

메인 파일 : danwolfe.gms

$title Dantzig Wolfe 분해 및 그리드 컴퓨팅 (DANWOLFE,SEQ=328)

$onText
이 예에서는 잘 알려진 Dantzig Wolfe 분해 방법을 구현합니다. 이
방법은 계수 행렬이 있는 선형 계획의 구조를 활용합니다.
특별한 형태를 가지고 있습니다:

     B0 B1 B2 ... Bk
         A1
             A2
                .
                 .  아크

특정 모델은 Ak가 발생하는 다중 상품 네트워크 흐름 문제입니다.
상품 흐름에 해당하고 Bk는 아크 용량을 나타냅니다.

Dantzig, G B 및 Wolfe, P, 선형 분해 원리
프로그램. 운영연구 8(1960), 101-111.

키워드: 선형 계획법, Dantzig Wolfe 분해, 다중 상품 네트워크 흐름 문제,
          네트워크 최적화, 그리드 컴퓨팅
$offText

$eolCom //

$setDDList 노드 통신 최대 시간
$노드를 설정하지 않은 경우 $set 노드 20
$comm을 설정하지 않은 경우 $set comm 5
$maxtime을 설정하지 않은 경우 $set maxtime 100
$if errorfree $abort 잘못된 이중 대시 매개변수: --nodes=n --comm=n --maxtime=secs

세트
   나는 '노드' / n1*n%노드% /
   k '상품' / k1*k%comm% /
   e(i,i) '가장자리';

별칭(i,j);

매개변수
   cost(i,j) '에지 사용 비용'
   bal(k,i) '균형'
   kdem(k) '수요'
   cap(i,j) '번들 용량';

변수
   x(k,i,j) '다중 상품 흐름'
   z '목표';

양수 변수 x;

방정식
   defbal(k,i) '균형 제약 조건'
   defcap(i,j) '번들링 용량'
   defobj;

defobj.. z =e= sum((k,e), 비용(e)*x(k,e));

defbal(k,i).. sum(e(i,j), x(k,e)) - sum(e(j,i),x(k,e)) =e= bal(k,i);

defcap(e)..sum(k, x(k,e)) =l= cap(e);

모델 mcf '다중 상품 흐름 문제' / all /;

**** 무작위 인스턴스 만들기
스칼라
   이넘
   가장자리 밀도 / 0.3 /;

e(i,j) = 균일(0,1) < 가장자리 밀도;
e(i,i) = 아니오;
비용(e) = 균일(1,10);
cap(e) = 균일(50,100)*log(카드(k));

루프(k,
   kdem(k) = 균일(50,150);
   inum =uniformInt(1,card(i)); bal(k,i)$(ord(i) = inum) = kdem(k);
   inum =uniformInt(1,card(i)); bal(k,i)$(ord(i) = inum) = bal(k,i) - kdem(k);
   kdem(k) = sum(i$(bal(k,i) > 0), bal(k,i));
);

**** 무작위 모델이 가능한지 확인하세요
옵션 limRow = 0, limCol = 0, solPrint = 꺼짐,solveLink = %solveLink.callModule%;

lp를 사용하여 mcf min z를 해결합니다.

abort$(mcf.modelStat <> %modelStat.optimal%) '문제가 실현 가능하지 않습니다. 가장자리 밀도를 높이세요.'

매개변수 xsingle(k,i,j) '단일 해결';
xsingle(k,e) = x.l(k,e)$[x.l(k,e) > 1e-6];

디스플레이$(카드(i) < 30) xsingle;

**** 마스터 모델 정의
세트
   p '경로 ID' / p1*p100 /
   슬롯 사이트(k,p) '활성 경로'
   pe(k,p,i,j) '가장자리 경로 입사 벡터';

매개변수 pcost(k,p) '경로 비용';

양수 변수
   xp(k,p)
   여유(k);

방정식
   mdefcap(i,j) '번들 제약'
   mdefbal(k) '균형 제약'
   mdefobj '목표';

mdefobj.. z =e= sum(슬롯 사이트, pcost(슬롯 사이트)*xp(슬롯 사이트)) + sum(k, 999*slack(k));

mdefbal(k).. sum(슬롯 사이트(k,p), xp(슬롯 사이트)) + slack(k) =e= kdem(k);

mdefcap(e)..sum(pe(슬롯 사이트e), xp(슬롯 사이트)) =l= cap(e);

모델 마스터 / mdefobj, mdefbal, mdefcap /;

**** 가격 책정 모델 정의: 최단 경로
매개변수 ebal(i);

양수 변수 xe(i,j);

방정식
   pdefbal(i) '균형 제약'
   pdefobj '객관적';

pdefobj.. z =e= sum(e, (cost(e) - mdefcap.m(e))*xe(e));

pdefbal(i).. sum(e(i,j), xe(e)) - sum(e(j,i),xe(e)) =e= ebal(i);

모델 가격 책정 / pdefobj, pdefbal /;

**** 직렬 분해 방법
스칼라
   '루프 표시기' 완료
   iter '반복 카운터';

Set nextp(k,p) '추가할 다음 경로';

* 명확한 경로 데이터
완료 = 0;
반복 = 0;
슬롯 사이트(k,p) = 아니오;
pe(k,p,e) = 아니오;
pcost(k,p) = 0;
nextp(k,p) = 아니요;
nextp(k,'p1') = 예;

동안(완료되지 않음,
   iter = 반복 + 1;
   z를 최소화하는 lp를 사용하여 마스터를 해결합니다.
   완료 = 1;
   루프(k$kdem(k),
      ebal(i) = bal(k,i)/kdem(k);
      z를 최소화하는 lp를 사용하여 가격 책정을 해결합니다.
      가격.solPrint = %solPrint.quiet%;  // 모든 출력을 끕니다. fpr 가격 책정 모델
      if(mdefbal.m(k) - z.l > 1e-6, // 새 경로 추가
         슬롯 사이트(nextp(k,p)) = 예;
         pe(nextp(k,p),e) = round(xe.l(e));
         pcost(nextp(k,p)) = sum(pe(nextp,e), 비용(e));
         nextp(k,p) = nextp(k,p-1);  // 다음 무료 경로로 경로를 범프합니다.
         abort$(sum(nextp(k,p),1) = 0) 'p를 너무 작게 설정';
         완료 = 0;
      );
   );
);

abort$(abs(master.objVal - mcf.objVal) > 1e-3) '다른 목표 값', master.objVal, mcf.objVal;

매개변수 xserial(k,i,j);
xserial(k,e) = sum(pe(슬롯 사이트(k,p),e), xp.l(슬롯 사이트));

display$(카드(i) < 30) xserial;

**** 이제 그리드 옵션과 동일합니다.
매개변수 h(k) '모델 핸들';
가격.solveLink = %solveLink.asyncGrid%;
가격.solPrint = %solPrint.summary%;

* 명확한 경로 데이터
완료 = 0;
반복 = 0;
슬롯 사이트(k,p) = 아니오;
pe(k,p,e) = 아니오;
pcost(k,p) = 0;
nextp(k,p) = 아니요;
nextp(k,'p1') = 예;

동안(완료되지 않음,
   iter = 반복 + 1;
   z를 최소화하는 lp를 사용하여 마스터를 해결합니다.
   완료 = 1;
   가격.번호 = 0;
   루프(k$kdem(k),
      ebal(i) = bal(k,i)/kdem(k);
      z를 최소화하는 lp를 사용하여 가격 책정을 해결합니다.
      가격.solPrint = %solPrint.quiet%; // 가격 책정 모델의 모든 출력을 끕니다.
      h(k) = 가격 책정.핸들;
   );
   반복하다
      루프(k$h(k),
         if(handlecollect(h(k))),
            if(mdefbal.m(k) - z.l > 1e-6,
               슬롯 사이트(nextp(k,p)) = 예;
               pe(nextp(k,p),e) = round(xe.l(e));
               pcost(nextp(k,p)) = sum(pe(nextp,e), 비용(e));
               nextp(k,p) = nextp(k,p-1);
               abort$(sum(nextp(k,p),1) = 0) 'p를 너무 작게 설정';
               완료 = 0;
            );
            display$handledelete(h(k)) '핸들 삭제 문제' ;
            h(k) = 0;
         );
      );
      display$sleep(card(h)*0.1) '조금만 자세요';
   카드(h) = 0 또는 경과 시간 > %maxtime%까지;
   abort$(card(h) and timeelapsed <= %maxtime%) '모든 해결이 반환되지는 않음', h;
);

if(경과된 시간 > %maxtime%,
   'maxtime=%maxtime%이(가) 초과되어 알고리즘이 중단되었습니다!'를 표시합니다.
);

abort$(abs(master.objVal - mcf.objVal) > 1e-3 및 경과 시간 <= %maxtime%) '다른 목표 값', master.objVal, mcf.objVal;

매개변수 xgrid(k,i,j);
xgrid(k,e) = sum(pe(슬롯 사이트(k,p),e), xp.l(슬롯 사이트));

디스플레이$(카드(i) < 30) xgrid;

매개변수 xall '흐름 요약';
xall(k,e,'싱글') = xsingle(k,e);
xall(k,e,'serial') = xserial(k,e);
xall(k,e,'그리드') = xgrid(k,e);

옵션 xall:3:3:1;
xall을 표시합니다;