# Decision Optimization

View Only

## CPOptimizer sequence patterns #### Luca Di GasperoFri February 05, 2021 11:40 AM #### ALEX FLEISCHERSat February 06, 2021 01:48 AM #### Luca Di GasperoSat February 06, 2021 02:10 AM #### Wu JasonWed June 01, 2022 12:06 PM #### Wu JasonWed June 01, 2022 12:06 PM #### Renaud DumeurThu June 02, 2022 07:25 AM • #### 1.  CPOptimizer sequence patterns

Posted Fri February 05, 2021 11:40 AM
Hello everybody,

I am looking for a way to impose some constraints that will avoid specific patterns of task types on sequences (something like the regular constraints in other CP systems). Actually, it would be enough to be able to express some constraint on just the two previous tasks in the sequence (something like the "typeOfPrevOfPrev"). Do you have any idea on how to model it?

Luca

------------------------------
Luca Di Gaspero
------------------------------

• #### 2.  RE: CPOptimizer sequence patterns

Posted Sat February 06, 2021 01:48 AM
Edited by ALEX FLEISCHER Sat February 06, 2021 01:49 AM
Hi

could

https://github.com/AlexFleischerParis/opltipsandtricks/blob/master/positionofintervalinsequence.mod

from opl tips and tricks help ?

regards

------------------------------
[Alex] [Fleischer]
[EMEA CPLEX Optimization Technical Sales]
[IBM]
------------------------------

• #### 3.  RE: CPOptimizer sequence patterns

Posted Sat February 06, 2021 02:10 AM
Hi,

in general the GitHub resource is very interesting, however in the specific case there are optional intervals in the sequence, so I have to figure out how to map them.

Anyway, thanks a lot!

------------------------------
Luca Di Gaspero
------------------------------

• #### 4.  RE: CPOptimizer sequence patterns

Posted Wed June 01, 2022 12:06 PM
Hi, Luca

Did you find the way to avoid specific patterns?
actually the function like:
typeOfNextNext(seq, itvs[i])

For example, making the constraint:
typeOfNext(seq, itvs[i]) != typeOf[i] => typeOfNextNext(seq, itvs[i]) != typeOf[i]

----------------------------
Jason Wu
----------------------------

------------------------------
Wu Jason
------------------------------

• #### 5.  RE: CPOptimizer sequence patterns

Posted Wed June 01, 2022 12:06 PM
Hi,

I get some problem here, we can get the " next type of interval i " by function typeOfNext(seq,itvs[i])
Is there anyway to make the constraint like:

if( typeOfNext(seq,itvs[i]) != typeOf(itvs[i]) ) => typeOfNextNext(seq,itvs[i]) != typeOf(itvs[i])

By the way, thanks for the sharing!
----------------------------------------------
Jason Wu
----------------------------------------------

------------------------------
Wu Jason
------------------------------

• #### 6.  RE: CPOptimizer sequence patterns

Posted Thu June 02, 2022 07:25 AM
Dear Jason,

If you only want to constrain triplets in a sequence (for instance ensuring at least one interval  type differs), you can write something like:
``````    // if an interval has a prev of same type
// then ensure that its next will have a different type
forall(i in r) {
(typeOfPrev(seq, itvs[i], -1) != typeValue[i])
|| (typeOfNext(seq, itvs[i], -1) != typeValue[i]);
}​``````

I hope it helps.

------------------------------
Renaud Dumeur
------------------------------

• #### 7.  RE: CPOptimizer sequence patterns

Posted Thu June 02, 2022 08:36 AM
Edited by Renaud Dumeur Thu June 02, 2022 08:43 AM
Dear Jason,

You can simulate a typeOfNextNext expression by using a secondary sequence variable that will be used to get the  array index of the next interval of the sequence. Using this index, that you can determine the type of a successor/predecessor and follow the chained intervals in the sequence.

``````using CP;
int n = 10;
range r = 1..n;
range r0 = 0..n;
dvar interval itvs[i in r] size i;
// define a type for each interval (3 possible types)
int typeValue[r0] = [-1, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2 ];
// sequence for types
dvar sequence seq
in all(i in r)itvs[i]
types all(i in r)  typeValue[i];
// sequence for ordering
dvar sequence order in itvs types all(i in r) i;
dexpr int nextId[i in r0] = (i == 0 ? 0 : typeOfNext(order, itvs[i], 0));
dexpr int prevId[i in r0] = (i == 0 ? 0 : typeOfPrev(order, itvs[i], 0));

// used for printing the solution
dexpr int nextType[i in r] = typeOfNext(seq, itvs[i], -1);
dexpr int prevType[i in r] = typeOfPrev(seq, itvs[i], -1);

subject to {
// ensure the intervals do not overlap
noOverlap(seq);
// ensure the ordering of the two seqeuence is the same
sameSequence(seq, order);
// if an interval has a prev of same type
// then ensure that its next will have a different type
forall(i in r) {
(typeValue[i] != typeValue[nextId[i]])
|| (typeValue[i] != typeValue[nextId[nextId[i]]]);
}
}

execute {
writeln("itvs", itvs);
writeln("seq", seq);
writeln("order", order);
write("  index "); for(i = 1; i <= n; ++i) write("\t" + i); writeln();
write(" nextId "); for(i = 1; i <= n; ++i) write("\t" + nextId[i]); writeln();
write(" prevId "); for(i = 1; i <= n; ++i) write("\t" + prevId[i]); writeln();
write(" nextType "); for(i = 1; i <= n; ++i) write("\t" + nextType[i]); writeln();
write("typeValue "); for(i = 1; i <= n; ++i) write("\t" + typeValue[i]); writeln();
write(" prevType "); for(i = 1; i <= n; ++i) write("\t" + prevType[i]); writeln();
for(i = 1; i <= n; ++i)
if(prevType[i] == typeValue[i] && nextType[i] == typeValue[i])
print("ERROR: 3 consecutive intervals have the same type");
}

``````

I hope this helps.

------------------------------
Renaud Dumeur
------------------------------