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.

Keywords: mixed integer linear programming, linear recursive sequence, fitting,
          cryptographic application, logical constraints

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.

Keywords: mixed integer linear programming, linear recursive sequence, fitting,
          cryptographic application, logical constraints
$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;

Variable
   k(t) 'recursive sequence'
   z    'objective min differences';

Binary Variable k(t);

Equation
   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;
);