lrs.gms : Linear Recursive Sequence Optimization Model

**Description**

Given a sequence of 0 & 1 observations, {c(t)}, We wish to find the linear recursive sequence defined by: k(t) = k(t-n) xor k(t-(n-r)) (mod 2), for t = n+1,2, ... t that minimizes the number of disagreements between c(t) and k(t). note, once k(1), k(2), ..., k(n) are specified, then k(n+1), ..., k(t) are uniquely determined by the lrs. Thus, this model declares k(1), k(2), ..., k(n) as binary and k(t), t > n as continuous variables that will automatically assume binary values when k(1) thru k(n) are binary. This model is based on a client model from the area of cryptography. The model demonstrates the use of variablename.prior=INF to relax some elements of a discrete variable to fractional variable elements. Moreover, it shows how to formulate the logical XOR operator using mixed-integer linear programming.

**Reference**

- GAMS Development Corporation, Formulation and Language Example.

**Large Model of Type :** MIP

**Category :** GAMS Model library

**Main file :** lrs.gms

$title Linear Recursive Sequence Optimization Model (LRS,SEQ=312) $ontext Given a sequence of 0 & 1 observations, {c(t)}, We wish to find the linear recursive sequence defined by: k(t) = k(t-n) xor k(t-(n-r)) (mod 2), for t = n+1,2, ... t that minimizes the number of disagreements between c(t) and k(t). note, once k(1), k(2), ..., k(n) are specified, then k(n+1), ..., k(t) are uniquely determined by the lrs. Thus, this model declares k(1), k(2), ..., k(n) as binary and k(t), t > n as continuous variables that will automatically assume binary values when k(1) thru k(n) are binary. This model is based on a client model from the area of cryptography. The model demonstrates the use of variablename.prior=INF to relax some elements of a discrete variable to fractional variable elements. Moreover, it shows how to formulate the logical XOR operator using mixed-integer linear programming. $offtext SET t time horizon /1*350/, f(t) first N steps /1*48/; PARAMETER c(t); c(t) = uniform(0,1) > .3 ; SCALAR n, r /8/, n_minus_r; n = card(f); n_minus_r=n-r; VARIABLES k(t) recursive sequence z objective min differences Binary variable k(t) Equations obj Objective modup1(t) XOR upper bounding constraint for combination false false modup2(t) XOR upper bounding constraint for combination true false modlo1(t) XOR lower bounding constraint for combination false true modlo2(t) XOR lower bounding constraint for combination true true ; obj.. z =e= sum(t, k(t)$(c(t)=0) + (1-k(t))$(c(t)=1)) ; $ontext The following four constraints model an k(t) = k(t-n) XOR k(t-(n-r)) Here is a table of possible combinations and the binding constraint: binding constraint k(t-n) k(t-(n-r)) result XORup1 XORup2 XORlo1 XORlo2 0 0 0 x 1 0 1 x 0 1 1 x 1 1 0 x $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); model lrs /all/; * The first n variables of k are binary, the remaining are fractional. * We do not need to set prioropt=1 since the relaxation of the binary * variables is done independently of prioropt k.prior(t) = inf; k.prior(f) = 1; option optcr=0.0, optca=0.99, limrow=0, limcol=0; * In case mod(n,r)=0 we can decompose in r independent subproblems Equation objsub; scalar modnum; objsub .. z =e= sum(t$(mod(ord(t)-1,r)=modnum), k(t)$(c(t)=0) + (1-k(t))$(c(t)=1)) ; model lrssub /objsub, modup1, modup2, modlo1, modlo2/; if (mod(n,r), solve lrs using mip minimizing z; else for(modnum = 0 to r-1, solve lrssub using mip minimizing z; k.fx(t)$(mod(ord(t)-1,r)=modnum) = k.l(t); ); solve lrs using mip minimizing z; );