Originally posted by: MSaqib

Reformatting my question posted earlier to the forum. I wonder why I never noticed the help bar on the right.
Hello everyone
I have a decision variable in the form of an array of integers.

dvar 

int Map[S24][TIMES] in LOCATIONS;

where S24, TIMES and LOCATIONS are all ranges of integers.
I need a constraint on Map, so that at least n consecutive values in it must be the same. For example, if the solver assigns the value 13 to

Map[1][1]

then

Map[1][2], Map[1][3], ..., Map[1][2+n]

must also be 13.

Map[1][2+n+1] is free to take on any value, including 13

Supposing that

Map[1][2+n+1] takes on the value 2

then

Map[1][2+n+2], Map[1][2+n+3], ..., Map[1][2+n+1+n] must also take on the value 2.

Here, n is an integer model parameter, and of course, this sort of constraint must hold for Map[2][*], Map[3][*] etc as well.
Any help/pointers would be helpful.
Thanks and best regards
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Hello.

Here is a proposal how to model your problem. The idea is to add two more arrays of integer variables. Variables in the first array isSame takes value 0 or 1: 0 if there is a change of a value at given point or 1 if a chain of same values continues:

dvar 

int isSame[S24][TIMES];   isSame[s][1] == 1; forall (i in 2..maxTIMES) isSame[s][i] == (Map[s][i-1] == Map[s][i]);

The second array chainLength counts length of a chain ending at a given point. It is defined recursively: depending on value isSame the length of the chain either increase by one or it restarts from zero:

dvar 

int chainLength[S24][TIMES];   chainLength[s][1] == 1; forall (i in 2..maxTIMES) chainLength[s][i] == (isSame[s][i]*chainLength[s][i-1] + 1);

Now when we have variables for lengths of chains, we can add constraints. The idea is: every time we start a new chain (isSame variable is 0) then length of the previous chain must be at least n:

forall (i in 2..maxTIMES) (isSame[s][i] == 1) || (chainLength[s][i-1] >= n);

Furthemore chain can end also at maxTIMES. So we add a constraint saying that these chains must also have length at least n:

chainLength[s][maxTIMES] >= n;

Here is the full code:

using CP;   

int maxS24 = 24; 

int maxTIMES = 20;   range S24 = 1..maxS24; range TIMES = 1..maxTIMES; 

int n = 5; range LOCATIONS = 1..10;   dvar 

int Map[S24][TIMES] in LOCATIONS;   dvar 

int isSame[S24][TIMES]; dvar 

int chainLength[S24][TIMES];   constraints 
{ forall (s in S24) 
{ isSame[s][1] == 1; forall (i in 2..maxTIMES) isSame[s][i] == (Map[s][i-1] == Map[s][i]); chainLength[s][1] == 1; forall (i in 2..maxTIMES) chainLength[s][i] == (isSame[s][i]*chainLength[s][i-1] + 1); forall (i in 2..maxTIMES) (isSame[s][i] == 1) || (chainLength[s][i-1] >= n); chainLength[s][maxTIMES] >= n; 
} 
}   execute 
{ 

for (var s=1; s<= maxS24; s++) 
{ 

for (var i=1; i <= maxTIMES; i++) write(Map[s][i] + 
" "); writeln(); 
} 
}

Depending on other constraints in your model, you may try to use search phase to force CP Optimizer to search on primary variables Map and not on derived variables isSame and chainLength. However I don't think that it will be necessary.

Best regards, Petr
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: MSaqib

Thanks Petr. I'll try this out. By the way, I was modelling this using mathematical programming and had to use several auxiliary variable. I was told by someone that CP would have richer functionality to represent the runlength constraint more easily, perhaps without need for aux variables.
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: SystemAdmin

Note that isSame and chainLength doesn't have to be variables. In fact, they could be "dexpr int". However OPL is not able to handle recursion in dexpr declaration (but you could do it in C++).

In terms of propagation speed or memory, using dvar instead of dexpr makes almost no difference. The only significant difference is that with isSame and chainLength as variables, they could be instantiated before the Map variables during the search. Sometimes it could be advantageous, (depending on the other constraints in the model). If it is not advantageous, you can still use search phases.

Best regards, Petr
#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: MSaqib

Thanks again, Petr. I am unfamiliar for the most part with CP. It seems fascinating, though, and I think I'd read up on it soon.
#ConstraintProgramming-General
#DecisionOptimization