lrs.gms : 선형 재귀 시퀀스 최적화 모델

설명

0 및 1개의 관측치 시퀀스가 주어지면 c(t),
우리는 다음과 같이 정의된 선형 재귀 시퀀스를 찾고 싶습니다.

   k(t) = k(t-n) xor k(t-(n-r)) (mod 2), t = n+1,2, ... t인 경우

이는 c(t)와 k(t) 사이의 불일치 수를 최소화합니다.

참고로 k(1), k(2), ..., k(n)이 지정되면
k(n+1), ..., k(t)는 lrs에 의해 고유하게 결정됩니다.

따라서 이 모델은 k(1), k(2), ..., k(n)을 이진수로 선언합니다.
그리고 k(t), t > n은 자동으로
k(1)부터 k(n)까지가 이진수일 때 이진값을 가정합니다.

이 모델은 암호화 분야의 클라이언트 모델을 기반으로 합니다.

이 모델은 일부 요소를 완화하기 위해 Variablename.prior=INF를 사용하는 방법을 보여줍니다.
이산변수를 분수변수 요소로 변환합니다. 게다가 그 방법을 보여준다.
혼합 정수 선형 프로그래밍을 사용하여 논리 XOR 연산자를 공식화합니다.

키워드: 혼합 정수 선형 계획법, 선형 재귀 수열, 피팅,
          암호화 응용 프로그램, 논리적 제약 조건

대형 모델 유형 :MIP

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

메인 파일 : lrs.gms

$title 선형 재귀 시퀀스 최적화 모델(LRS,SEQ=312)

$onText
0과 1개의 관측값 시퀀스가 주어지면 c(t),
우리는 다음과 같이 정의된 선형 재귀 시퀀스를 찾고 싶습니다.

   k(t) = k(t-n) xor k(t-(n-r)) (mod 2), t = n+1,2, ... t인 경우

이는 c(t)와 k(t) 사이의 불일치 수를 최소화합니다.

참고로 k(1), k(2), ..., k(n)이 지정되면
k(n+1), ..., k(t)는 lrs에 의해 고유하게 결정됩니다.

따라서 이 모델은 k(1), k(2), ..., k(n)을 이진수로 선언합니다.
그리고 k(t), t > n은 자동으로
k(1)부터 k(n)까지가 이진수일 때 이진값을 가정합니다.

이 모델은 암호화 분야의 클라이언트 모델을 기반으로 합니다.

이 모델은 일부 요소를 완화하기 위해 Variablename.prior=INF를 사용하는 방법을 보여줍니다.
이산변수를 분수변수 요소로 변환합니다. 게다가 그 방법을 보여준다.
혼합 정수 선형 프로그래밍을 사용하여 논리 XOR 연산자를 공식화합니다.

키워드: 혼합 정수 선형 계획법, 선형 재귀 수열, 피팅,
          암호화 응용 프로그램, 논리적 제약 조건
$offText

세트
   t '시간 범위' / 1*350 /
   f(t) '첫 번째 N 단계' / 1*48 /;

매개변수 c(t);
c(t) = 균일(0,1) > .3;

스칼라
   엔
   r / 8 /
   n_minus_r;

n = 카드(f);
n_minus_r = n - r;

변수
   k(t) '재귀 시퀀스'
   z '객관적인 최소 차이';

이진변수 k(t);

방정식
   obj '목표'
   modup1(t) '조합에 대한 XOR 상한 제약 조건 false false'
   modup2(t) '조합에 대한 XOR 상한 제약 조건 true false'
   modlo1(t) '조합에 대한 XOR 하한 경계 제약 조건 false true'
   modlo2(t) '조합에 대한 XOR 하한 제약 조건 true true';

obj.. z =e= sum(t, k(t)$(c(t) = 0) + (1 - k(t))$(c(t) = 1));

$onText
다음 네 가지 제약 조건은 k(t) = k(t-n) XOR k(t-(n-r))을 모델링합니다.
다음은 가능한 조합과 바인딩 제약 조건에 대한 표입니다.
                              바인딩 제약
k(t-n) k(t-(n-r)) 결과 XORup1 XORup2 XORlo1 XORlo2
  0 0 0x
  1 0 1x
  0 1 1x
  1 1 0x
$offText

modup1(t-n).. k(t) =l= k(t-n) + k(t-n_minus_r);
modup2(t-n).. k(t) =l= 2 - k(t-n) - k(t-n_minus_r);
modlo1(t-n).. k(t) =g= - k(t-n) + k(t-n_minus_r);
modlo2(t-n).. k(t) =g= k(t-n) - k(t-n_minus_r);

모델 lrs / 모두 /;

* k의 처음 n개 변수는 이진 변수이고 나머지는 분수 변수입니다.
* 바이너리가 완화되었으므로 Prioropt=1로 설정할 필요가 없습니다.
* 변수는 Prioropt와 독립적으로 수행됩니다.
k.prior(t) = inf;
k.prior(f) = 1;

옵션 optCr = 0.0, optCa = 0.99, limRow = 0, limCol = 0;

* mod(n,r) = 0인 경우 r개의 독립 하위 문제로 분해할 수 있습니다.
방정식 objsub;

스칼라 모드넘;

objsub.. z =e= sum(t$(mod(ord(t) - 1,r) = modnum), k(t)$(c(t) = 0) + (1 - k(t))$(c(t) = 1));

모델 lrssub / objsub, modup1, modup2, modlo1, modlo2 /;

if(mod(n,r),
   z를 최소화하는 mip를 사용하여 lrs를 해결합니다.
그렇지 않으면
   for(modnum = 0 ~ r - 1,
     z를 최소화하는 mip를 사용하여 lrssub를 해결합니다.
     k.fx(t)$(mod(ord(t) - 1,r) = modnum) = k.l(t);
   );
   z를 최소화하는 mip를 사용하여 lrs를 해결합니다.
);