Decision Optimization

 View Only
  • 1.  CP Optimizer: wrong solution when use noOverlap constraint, transition matrix and isDirect=1

    Posted Thu June 02, 2022 06:44 AM
    Hi everyone,

    I have found the situation when function noOverlap with flag isDirect=1 works incorrect. The solution should be a=[0, 5), b=[5, 10), c=[10, 15). But the model gives a=[0, 5), b=[5, 10), c=[25, 30) - as if I use isDirect=0.
    It is a bug or maybe I'm doing smth wrong?

    Model:
    using CP;

    tuple changes_type{ int id1; int id2; int value; };
    {changes_type} changes = { <1, 3, 20> };

    dvar interval a size 5;
    dvar interval b size 5;
    dvar interval c size 5;

    dvar sequence seq in append(a, b, c) types append(1, 2, 3);

    minimize endOf(c);

    subject to {

    noOverlap(seq, changes, true);

    startBeforeStart(a, b);
    startBeforeStart(b, c);
    }

    CPLEX version: 20.1.0.0

    ------------------------------
    Rustam Salikhov
    ------------------------------


  • 2.  RE: CP Optimizer: wrong solution when use noOverlap constraint, transition matrix and isDirect=1

    Posted Thu June 02, 2022 09:14 AM
    Edited by Renaud Dumeur Thu June 02, 2022 09:21 AM
    Dear Rustam,
    This is weird. I need to have a closer look at this.
    Cheers,
    ------------------------------
    Renaud Dumeur
    ------------------------------



  • 3.  RE: CP Optimizer: wrong solution when use noOverlap constraint, transition matrix and isDirect=1

    Posted Thu June 02, 2022 10:24 AM
    Dear Rustam,

    It really looks like a bug happening when a single transition time is specified.
    I've added an extra interval and a transition time of 1 to it, and with isDirect=true, we have a correct solution:
    using CP;
    
    tuple changes_type{ int id1; int id2; int value; };
    {changes_type} changes = { <1, 3, 20>, <3,4,1> };
    //{changes_type} changes = { <1, 3, 20> };
    
    dvar interval a size 5;
    dvar interval b size 5;
    dvar interval c size 5;
    dvar interval d size 5;
    
    dvar sequence seq in append(a, b, c, d) types append(1, 2, 3, 4);
    
    minimize endOf(c);
    
    subject to {
    
    noOverlap(seq, changes, true);
    
    startBeforeStart(a, b);
    startBeforeStart(b, c);
    startBeforeStart(c, d);
            }
    
            execute {
    
                 writeln("a", a);
                 writeln("b", b);
                 writeln("c", c);
                 writeln("d", d);
                 }
            
    ​

    but note that a zero duration transition from c to d would trigger the bug again.
    Thank you for notifying us.
    Cheers,



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



  • 4.  RE: CP Optimizer: wrong solution when use noOverlap constraint, transition matrix and isDirect=1

    Posted Fri June 03, 2022 05:38 AM
    Edited by Rustam Salikhov Tue June 07, 2022 04:27 AM
    Dear Renaud,

    Thank you for your support. I hope it will be easy to fix it.

    I wanted to continue the investigation and I've written the model using docplex (Python API). It was surprised me - the solution was correct. Maybe it can help you to investigate the reason of the solver behaviour when the model is written on OPL.

    Here is my code:

    import docplex.cp.model as cp_model
    
    
    changes = [[0, 0, 20], [0, 0, 0], [0, 0, 0]]
    
    mdl = cp_model.CpoModel("NoOverlap, transition matrix, isDirect=1")
    
    a = mdl.interval_var(name="a", size=5)
    b = mdl.interval_var(name="b", size=5)
    c = mdl.interval_var(name="c", size=5)
    
    seq = mdl.sequence_var(name="seq", vars=[a, b, c], types=[0, 1, 2])
    
    mdl.add(mdl.minimize(mdl.end_of(c)))
    
    mdl.add(mdl.no_overlap(seq, changes, True))
    mdl.add(mdl.start_before_start(a, b))
    mdl.add(mdl.start_before_start(b, c))
    
    msol = mdl.solve(trace_log=False)
    
    if msol is not None and msol.is_solution():
        print("{}".format(msol.get_var_solution(a)))
        print("{}".format(msol.get_var_solution(b)))
        print("{}".format(msol.get_var_solution(c)))
    ​

    Regards,

    ------------------------------
    Rustam Salikhov
    ------------------------------



  • 5.  RE: CP Optimizer: wrong solution when use noOverlap constraint, transition matrix and isDirect=1

    Posted Fri June 03, 2022 12:21 PM
    Dear Rustam,

    We indeed can see by comparing the generated .cpo models is that the transition matrix generated by OPL differs from the one produced by the python model. 
    Thank you for the information, it helps us a lot.
    Cheers,

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