설명

이 모델은 일반화된 2차 할당 문제를 해결합니다.
(GQAP)은 다양한 볼록화 방법을 사용합니다. GQAP는 다음과 같이 설명합니다.
광범위한 종류의 2차 정수 계획법 문제, 여기서
I pair-wise 관련 장비는 제한된 N 위치에 할당됩니다.
이를 수용할 수 있는 위치의 능력에 따라 결정됩니다.

Cplex에는 다음과 같은 경우 MIQP에 대한 내장형 볼록화 방법이 있습니다.
2차 항에는 이진 변수만 포함됩니다. 다른 방법
준정사 계획법의 해가 필요합니다.

대형 모델 유형 :RMIQCP

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

메인 파일 : gqapsdp.gms   다음을 포함합니다: pb16x7.inc

$title SDP 일반화된 2차 할당 문제의 Convexification(GQAPSDP,SEQ=339)

$onText
이 모델은 일반화된 2차 할당 문제를 해결합니다.
(GQAP)은 다양한 볼록화 방법을 사용합니다. GQAP는 다음과 같이 설명합니다.
광범위한 종류의 2차 정수 계획법 문제, 여기서
I pair-wise 관련 장비는 제한된 N 위치에 할당됩니다.
이를 수용할 수 있는 위치의 능력에 따라 결정됩니다.

Cplex에는 다음과 같은 경우 MIQP에 대한 내장형 볼록화 방법이 있습니다.
2차 항에는 이진 변수만 포함됩니다. 다른 방법
준정의 프로그램의 해가 필요합니다.

Plateau M.C., Reformulations Quadratiques pour la
프로그래밍 쿼드러티크 및 변수 0-1. 박사 논문,
국립음악원, CEDRIC, 2006.

Guignard, M., 고원 볼록화 방법 확장
비볼록 이차 0-1 프로그램. 기술. 대표, 와튼 스쿨, 2008.

키워드: 완화된 혼합 정수 2차 제약 조건 프로그래밍, 2차
          할당 문제, 볼록화 방법, 준정의 계획법
$offText

세트
   나는 '장비'
   j '위치';

별칭 (i,ip), (j,jp);

매개변수
   install(i,j) '설치 비용'
   flow(i,ip) '교환량'
   단위 '흐름 단위'
   dist(j,jp) '거리'
   a(i) '크기'
   b(j) '용량';

$인스턴스를 설정하지 않은 경우 $set 인스턴스 pb16x7.inc
$include %instance%

if(card(i)*card(j)>20, 옵션 limrow=0,limcol=0);

* 볼록화 옵션: cplex, u, uv, au, uav
$설정되지 않은 경우 선택 $set 선택 u
$if '%opt%'==u $goTo optok
$if '%opt%'==uv $goTo optok
$if '%opt%'==ua $goTo optok
$if '%opt%'==uav $goTo optok
$if '%opt%'==cplex $goTo optok
$abort --opt=%opt% 그러나 u|uv|ua|uav|cplex여야 합니다.
$라벨 옵톡

$set dou 0
$set dov 0
$set doa 0
$if '%opt%'==cplex $goTo nosdp

$eval imax 카드(i)
$eval jmax 카드(j)
$eval xmax %imax%*%jmax%

$set dou 1
$ifThen %opt%==uv
$ 세트 dov 1
$elseIf %opt%==ua
$ 세트 도아 1
$elseIf %opt%==uav
$ 세트 dov 1
$ 세트 도아 1
$elseIf %opt%==u
$else
$ opt=%opt%에 대한 누락된 테스트를 중단합니다.
$endIf

n 'SDP 변수' / 1*%xmax%, 0 / 설정;
별칭(n, np, m);

set map(n,i,j) 'n을 (i,j)에 매핑';
map(n,i,j) = (ord(n) = (ord(i)-1) * %jmax% + ord(j));

변수 Y(n,n) 'PSDMATRIX'
          sdpz '객관 변수'
;

방정식 sdpobj '목적 함수'
          sdpsign(i) '원래 할당 제약'
          sdp할당1(i,ip,jp) 'x(ip,jp)를 곱한 할당 제약'
          sdp할당2 '할당 제약 조건의 합에 자신을 곱함'
          sdpcapacity(j) '장비 할당 시 위치 용량'
          sdpmatrixident(n) 'SDP 매트릭스의 ID'
;

sdpobj.. sdpz =e= sum((i,j,ip,jp,n,np)$(map(n,i,j) 및 map(np,ip,jp)), (Y(n,np)+Y(np,n))*(unit*flow(i,ip)*dist(j,jp)) / 2.0)
                + sum(map(n,i,j), install(i,j) * (Y(n,'0') + Y('0',n)) / 2.0)
                + eps*sum((n,np),Y(n,np));

sdp할당(i).. sum(map(n,i,j), Y(n,'0') + Y('0',n)) / 2.0 =e= 1;

sdp할당1(i,ip,jp).. sum((j,n,np)$(map(n,i,j) 및 map(np,ip,jp)), (Y(n,np) + Y(np,n)) / 2.0) =e= sum(map(np,ip,jp), Y(np,'0') + Y('0',np)) / 2.0;

sdpsign2.. sum(i, sum((j,jp,n,np)$(map(n,i,j) 및 map(np,i,jp)), Y(n,np) + Y(np,n)) / 2.0 
  - sum((j,n)$map(n,i,j), Y(n,'0') + Y('0',n)) + 1) =e= 0;

sdpcapacity(j).. sum(map(n,i,j), a(i)*(Y(n,'0') + Y('0',n))/2.0) =l= b(j);

sdpmatrixident(n)$(not sameas(n,'0')).. Y(n,n) =e= (Y(n,'0') + Y('0',n)) / 2.0;

Y.fx('0','0') = 1.0;

모델 sdp / sdpobj, sdp할당, sdpcapacity,
$if %dou% == 1 sdpmatrixident
$if %doa% == 1 sdp할당1
$if %dov% == 1 sdp할당2
/;
sdp.dictfile = 1;

옵션 lp = 모세크;
lp를 사용하여 sdp min sdpz를 해결합니다.

매개변수
   u(i,j) 'X_ijij의 쌍대 = xij'
   alpha(ip,i,j) '대입 제약 조건의 이중'
   v '|Ax-b|의 이중';

$if %dou%==1 u(i,j) = -sum(n$map(n,i,j), sdpmatrixident.m(n));
$if %doa%==1 alpha(ip,i,j) = -sdp할당1.m(ip,i,j);
$if %dov%==1 v = -sdp할당2.m;

$라벨 nosdp
변수
   x(i,j) '장비 i가 위치 j에 할당되었습니다.'
   z '총 비용';

이진변수 x;

방정식
   defcost '목적 함수'
   할당(i) '각 장비를 위치에 할당'
   용량(j) '장비 할당 시 위치 용량';

defcost.. z =e= sum((i,j,ip,jp), x(i,j)*(unit*flow(i,ip)*dist(j,jp))*x(ip,jp))
             + 합계((i,j), 설치(i,j)*x(i,j))
$if %dou%==1 + sum((i,j), (u(i,j)*1.01)*(sqr(x(i,j)) - x(i,j)))
$if %doa%==1 + sum((ip,i,j), alpha(ip,i,j)*x(i,j)*(sum(jp,x(ip,jp)) - 1))
$if %dov%==1 + v*sum(i, sqr(sum(j,x(i,j)) - 1))
;

할당(i).. 합계(j, x(i,j)) =e= 1;

용량(j).. sum(i, a(i)*x(i,j)) =l= b(j);

모델 gqap / defcost, 할당, 용량 /;

rmiqcp min z를 사용하여 gqap을 해결합니다.