설명

k차원 반경 구의 최대 개수 결정
반경 r의 중심 구에 인접할 수 있는 r은 알려져 있습니다.
키스 수 문제(KNP)로 알려졌습니다. 문제가 해결되었습니다.
2(6), 3(12) 차원, 최근에는 4(24) 차원의 경우입니다. 여기
비선형(비볼록) 수학적 프로그래밍 모델로 알려져 있습니다.
KNP 해에 대한 거리 공식입니다. 우리는 해결
Variable Neighborhood Search 알고리즘을 사용하여 문제를 해결합니다.

https://en.wikipedia.org/wiki/Kissing_number_problem

Kucherenko, S, Belotti, P, Liberti, L 및 Maculan, N,
키스 수 문제에 대한 새로운 공식.
이산 응용 수학, 155:14, 1837--1841, 2007.
https://doi.org/10.1016/j.dam.2006.05.012

키워드: 비선형 계획법, 키스 수 문제, 변수 이웃 검색,
          전역 최적화, 구형 패킹, 수학

대형 모델 유형 :NLP

카테고리 : 슬롯 무료체험 모델 라이브러리

메인 파일 : knp.gms

변수 이웃 검색을 사용한 $title 키스 번호 문제 (KNP,SEQ=321)

$onText
k차원 반경 구의 최대 수 결정
반경 r의 중심 구에 인접할 수 있는 r은 알려져 있습니다.
키스 수 문제(KNP)로 알려졌습니다. 문제가 해결되었습니다.
2(6), 3(12) 차원, 최근에는 4(24) 차원의 경우입니다. 여기
비선형(비볼록) 수학적 프로그래밍 모델로 알려져 있습니다.
KNP 해에 대한 거리 공식입니다. 우리는 해결
Variable Neighborhood Search 알고리즘을 사용하여 문제를 해결합니다.

https://en.wikipedia.org/wiki/Kissing_number_problem

Kucherenko, S, Belotti, P, Liberti, L 및 Maculan, N,
키스 수 문제에 대한 새로운 공식.
이산 응용 수학, 155:14, 1837--1841, 2007.
https://doi.org/10.1016/j.dam.2006.05.012

키워드: 비선형 계획법, 키스 수 문제, 변수 이웃 검색,
          전역 최적화, 구 패킹, 수학
$offText

$eolCom //

$희미하게 설정되지 않은 경우 $set 희미 4
$nspheres를 설정하지 않은 경우 $set nspheres 24

세트
   k '차원' / k1*k%dim% /
   i '구' / s1*s%nspheres% /;

별칭(i,j);

변수
   x(i,k) '중앙 구 주위의 i번째 구 중심 위치'
   z '타당성 지표';

방정식
   eq1(i) '구 중심은 중심 구로부터 거리 2를 가집니다.'
   eq2(i,j) '최소 쌍별 구 분리 거리';

eq1(i)..sum(k, sqr(x(i,k))) =e= 4;

eq2(i,j)$(ord(i) < ord(j)).. sum(k, sqr(x(i,k) - x(j,k))) =g= 4*z;

모델 키스 / 모두 /;

스칼라
   로 / -2 /
   위로 / 2 /;

x.lo(i,k) = lo;
x.up(i,k) = 위로;
x.l(i,k) = 균일(lo,up);

매개변수
   p(i,k) '최적 해의 중심점'
   bestobj '최상의 솔루션의 타당성 지표' / 0 /
   bestbnd '최적값에 대한 최선의 경계' / inf /
   maxnk '주요 반복 제한(검색 공간)' / 20 /
   maxns '사소한 반복 제한(무작위 시작)' / 5 /
   nk '주요 반복' / 1 /
   ns '사소한 반복';

Kissing.solveLink = %solveLink.callScript%;

nlp를 사용하여 키스 최대 z를 해결합니다.

* 솔루션을 최상의 솔루션으로 저장
if(kissing.modelStat = %modelStat.locallyOptimal% 또는
   Kissing.modelStat = %modelStat.optimal% 또는
   Kissing.modelStat = %modelStat.feasibleSolution%,
   bestobj = z.l;
   p(i,k) = x.l(i,k);
그렇지 않으면
* 해결책이 없으면 VNS를 시작하지 마십시오.
   최대nk = 0;
);

* 가능한 경우 이중 바인딩을 저장합니다.
bestbnd$(kissing.objEst <> na) = min(bestbnd, Kissing.objEst);

* 가변 동네 검색 알고리즘
옵션 solPrint = 꺼짐, limRow = 0, limCol = 0;

while(nk <= maxnk 및 bestobj < 1 및 bestbnd >= 1 및 Kissing.solveStat <> %solveStat.userInterrupt%,
   ns = 1;
   반복하다
      // 최적 지점 근처에서 새로운 지점을 샘플링합니다.
      x.l(i,k) = 균일(p(i,k) - nk*(p(i,k) - lo)/maxnk, p(i,k) + nk*(up - p(i,k))/maxnk);

      nlp를 사용하여 키스 최대 z를 해결합니다.

      // 해결책이 없는 경우 z.l이 bestobj 업데이트를 피할 수 있을 만큼 충분히 작은지 확인하세요.
      z.l$(kissing.modelStat <> %modelStat.optimal% 및
           Kissing.modelStat <> %modelStat.feasibleSolution% 및
           Kissing.modelStat <> %modelStat.locallyOptimal%) = bestobj - 1;

      // 이중 바운드 업데이트
      bestbnd$(kissing.objEst <> na) = min(bestbnd,kissing.objEst);
      ns = ns + 1;
   Until(ns = maxns + 1) 또는 (z.l > bestobj) 또는 (bestbnd < 1) 또는 (kissing.solveStat = %solveStat.userInterrupt%);

   if(z.l <= bestobj,
      // 이웃을 확대하고 다시 작은 반복을 수행합니다.
      nk = nk + 1;
   그렇지 않으면
      // 최적 경계, 최신 이웃을 업데이트하고 작은 이웃으로 다시 시작
      bestobj = z.l;
      p(i,k) = x.l(i,k);
      nk = 1;
   );
   bestbnd, bestobj를 표시합니다.
);

if(bestobj >= 1,
   'KNP(%dim%) >= %nspheres%'를 표시합니다.
elseIf bestbnd < 1,
   'KNP(%dim%) < %nspheres%'를 표시합니다.
elseIf nk > maxnk,
   '가능성이 가장 높음: KNP(%dim%) < %nspheres%'를 표시합니다.
elseIf maxnk = 0,
   '초기 NLP를 해결할 수 없음'을 표시합니다.
그렇지 않으면
   'VNS가 중단되었습니다'를 표시합니다.
);