Decision Optimization

 View Only
  • 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?

    Thanks in advance,

    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
    ------------------------------