nemhaus.gms : 상호작용 비용을 최소화하기 위한 스케줄링

설명

활동은 다양한 시설에서 예약될 수 있습니다. 활동이 2개인 경우
동일한 시설에서 예약된 경우 상호 작용 비용이 발생합니다. 이
원래는 0/1 이차 계획법 문제로 공식화되었습니다.
또한 MIP 공식을 탐색하고 모델을 해결합니다.
가능한 모든 시설에 대해.

소형 모델 유형 :MIP nlp

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

메인 파일 : nemhaus.gms

상호작용 비용을 최소화하기 위한 $title 예약 (NEMHAUS,SEQ=194)

$onText
활동은 다양한 시설에서 예약될 수 있습니다. 활동이 2개인 경우
동일한 시설에서 예약된 경우 상호 작용 비용이 발생합니다. 이
원래는 0/1 이차 계획법 문제로 공식화되었습니다.
또한 MIP 공식을 탐색하고 모델을 해결합니다.
가능한 모든 시설을 위해.

Carlson, RC 및 Nemhauser, GL, 상호 작용 비용을 최소화하기 위한 일정 수립.
운영연구 14(1966), 52-58.

키워드: 비선형 계획법, 혼합 정수 선형 계획법, 스케줄링,
          할당 문제
$offText

$eolCom //

세트
   나는 '활동'
   jj '시설'
   j(jj) '시설의 동적 하위 집합';

별칭(i,k);

매개변수 a(i,k) '동일 시설에서 활동 i와 k를 예약하는 비용';

변수
   z '총 상호작용 비용'
   x(i,jj) 'j 시설에 예정된 활동 i'
   y(i,jj,k) 'xx*x의 곱'
   xb(i,jj) 'x의 0-1 버전';

이진변수 xb;
양수 변수 x, y;

방정식
   zdef '객관적 정의'
   sch(i) '모든 활동 예약'
   bzdef '객관적 정의'
   bsch(i) '바이너리 버전 일정'
   ydef(i,jj,k) '제품 정의';

모델
   하나의 'QP 공식' / zdef, sch /
   두 개의 'MIP 공식화' / bzdef, bsch, ydef /;

zdef.. z =e= sum((i,j,k), x(i,j)*a(i,k)*x(k,j));

sch(i)..sum(j, x(i,j)) =e= 1;

bzdef.. z =e= sum((i,j,k), a(i,k)*y(i,j,k));

bsch(i)..sum(j, xb(i,j)) =e= 1;

ydef(i,j,k)$a(i,k)..y(i,j,k) =g= xb(i,j) + xb(k,j) - 1;

* 원본 데이터
세트
   나는 'j' / 막-1*막-5 /
   jj / fac-1*fac-5 /;

테이블 a(i,k) '상호작용 비용'
           1막 1막 2막 3막 4막 5막
   막-1 2 4 3
   2막 6 2 3
   3막 2 6 5 3
   4막 4 2 5 3
   막-5 3 3 3 3 ;

$onText
다음과 같은 경우에는 NLP에 대한 로컬 솔루션을 참고하세요.
4개 시설:
로컬 최적 상호 작용 비용 = 1.5
(액트-1,액트-2).fac-1 1.0000
(액트-3,액트-5).fac-2 0.5000
(액트-4).fac-3 1.0000
(액트-3,액트-5).fac-4 0.5000

전역 최적 상호 작용 비용 = 0.0
(액트-1,액트-2).fac-1 1.0000
(액트-3).fac-2 1.0000
(액트-4).fac-3 1.0000
(액트-5).fac-4 1.0000
$offText

* 20가지 활동 데이터 세트
$onText
세트
   나는 'j' / a-01*a-20 /
   jj / f-01*f-20 /;

테이블 a(i,k) '상호작용 비용'
          a-01 a-02 a-03 a-04 a-05 a-06 a-07 a-08 a-09 a-10 a-11 a-12 a-13 a-14 a-15 a-16 a-17 a-18 a-19 a-20
   a-01 8 4 18 8 3 19 4 17 6 9 7 6 10 5 7
   a-02 8 4 7 1 5 11 10 4 10 2 7 4 13 4 7
   가-03 4 3 1 5 9 16 5 15 4 4 9 3 7 14
   가-04 3 2 3 4 11 1 9 3 2 9 1 7 5 6 3
   가-05 4 2 4 9 17 13 1 1 14 2 12 7 1 4
   가-06 7 1 3 4 5 13 1 2 6 2 1 13 4
   가-07 1 5 4 5 10 9 14 4 4 5 8 4 5 5 1
   가-08 18 5 9 11 9 5 13 7 3 6 5 12 4 7 5
   가-09 8 11 16 1 10 9 2 10 10 3 7 3 3 11 4 7
   가-10 3 17 13 9 5 9 14 6 14 8 2 1 7 4 1 3
   가-11 19 5 9 13 1 14 13 2 14 6 11 11 11 9 5 4
   가-12 4 10 15 3 1 2 4 7 10 6 6 6 11 6 10 8 4 6 9
   가-13 17 4 4 2 1 6 10 14 11 6 16 7 17 5
   가-14 6 10 9 14 2 4 3 3 8 11 5 10 10 3 9 6
   가-15 9 2 1 2 1 5 6 7 2 11 6 16 5 12 18 13 8 9
   가-16 7 7 4 7 12 13 8 5 3 1 11 10 7 10 12 14 5 5 11
   가-17 6 4 9 5 4 12 3 7 8 17 10 18 14 8 2
   가-18 10 13 3 7 5 4 11 4 9 4 3 13 5 6
   가-19 5 4 7 6 1 5 7 4 1 5 6 5 9 8 5 8 3
   가-20 7 7 14 3 4 4 1 5 7 3 4 9 6 9 11 2 6 3 ;
$offText

* 무작위 데이터 만들기
$onText
i / a-01*a-20 /를 설정합니다.
     jj / f-01*f-20 /;

a(i,k) = max(0,uniform(-5,10));
a(i,k) = round(a(i,k) + a(k,i));
a(i,i) = 0;
$offText

a(i,k)$(ord(i) > ord(k)) = 0;  // 대칭 활용

// 전역 옵션 설정
option limCol = 0 // 활동 목록 없음
       limRow = 0 // 행 목록 없음
       resLim = 10 // 솔버의 최대 실행 시간 설정
       optCr = 0.001 // 밉 상대 기준 설정
       solPrint = 꺼짐;      //solprint 끄기

매개변수 objval(jj,*) '목표값';

스칼라 더;

// 충돌이 없을 때까지 시설을 확장합니다.
j(jj) = 아니오;
더 = 1;
루프(jj$more,
   j(jj) = 그렇습니다;

   nlp min z를 사용하여 문제를 해결하세요.
   objval(jj,'nlp') = z.l;
   더 = z.l;

   mip min z를 사용하여 두 가지를 해결합니다.
   objval(jj,'mip') = z.l;
   더 = 더 또는 z.l;
);

표시 objval;