IC5Notice: We have upgraded developerWorks Community to the latest version of IBM Connections. For more information, read our upgrade FAQ.
Topic
  • 10 replies
  • Latest Post - ‏2014-01-29T20:58:29Z by s.st1led
s.st1led
s.st1led
16 Posts

Pinned topic Strange solver behavior using dexprs with count/all syntax and tuples

‏2014-01-21T18:03:05Z |

Hi everybody, I'm using CPLEX Optimization Studio 12.6 x64 on Windows 8.1 x64 and I noticed a strange behavior using the all syntax over arrays indexed by tuples.

Consider the following constraint model:

using CP;

range T = 0..4;

tuple Task {
    key string id;
    int duration;
}

tuple TaskExecution {
    Task task;
    int execution;
}

tuple TaskExecutionIndex {
    TaskExecution task_execution;
    int index;
}

{Task} J = {<"j0",2>, <"j1",3>};
{TaskExecution} A = {<j,x> | j in J, x in 0..0};
{TaskExecutionIndex} AP = {<a,p> | a in A, p in 0..a.task.duration-1};


dvar int task_executions[j in J] in T;
dvar int active[ap in AP] in T;

dexpr int active_task[j in J, t in T] = count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t);
dexpr int load[t in T] = sum(j in J) active_task[j, t];

subject to{

    forall(t in T)
        c1: load[t] <= 1;
        
        
    c2: active[<<<"j0",2>,0>,0>] == 0;
    c3: active[<<<"j0",2>,0>,1>] == 1;
    c4: active[<<<"j1",3>,0>,0>] == 0;
    c5: active[<<<"j1",3>,0>,1>] == 3;
    c6: active[<<<"j1",3>,0>,2>] == 4;
    
    c7: task_executions[<"j0",2>] == 1;
    c8: task_executions[<"j1",3>] == 1;
}

The constraints c1-c8 are used in this example to assign some values to the variables active and task_executions. Clearly, load[0] == 2 in contrast with the constraint c1, but still the problem is deemed feasible by CP. This also happens if I explicitly state that load[0] should be equal to 2, for instance by adding a last line in the subject to block: c9: load[0] == 2;. It's like CP is ignoring the constraints where load is present.

Moreover, if I remove the constraints c2-c8 and replace c1:load[t] <= 1 with c1: load[t] == 1, CP deems that the problem is infeasible, while it clearly is feasible. For instance, a solution has the following assignments:

    c2: active[<<<"j0",2>,0>,0>] == 0;
    c3: active[<<<"j0",2>,0>,1>] == 1;
    c4: active[<<<"j1",3>,0>,0>] == 2;
    c5: active[<<<"j1",3>,0>,1>] == 3;
    c6: active[<<<"j1",3>,0>,2>] == 4;
    
    c7: task_executions[<"j0",2>] == 1;
    c8: task_executions[<"j1",3>] == 1;

Indeed, if once again I remove c1: load[t] == 1 and keep these new c2-c8, I get the expected solution where load = [1,1,1,1,1], that clearly respects c1. Again, here it looks like CP deems unfeasible every problem with an equality constraint on the dexpr load.

What is going on here? I guess there's something big that I'm missing on how count/all works in dexprs.

 

Regards,

Stefano

Updated on 2014-01-21T18:04:16Z at 2014-01-21T18:04:16Z by s.st1led
  • ChrisBr
    ChrisBr
    40 Posts
    ACCEPTED ANSWER

    Re: Strange solver behavior using dexprs with count/all syntax and tuples

    ‏2014-01-27T17:32:14Z  
    • s.st1led
    • ‏2014-01-26T12:08:20Z

    Thank you, if I replace the count/all by the sum of binary variables, then the model correctly states that the first problem is unfeasible, and the second is feasible returning a solution. From the correctness point of view there's no problem here, and I would be more than happy to use this solution you proposed.

    However, I'm afraid that defining active_task as a sum of binary variables is very inefficient. Consider this final model:

    using CP;
    
    range T = 0..400;
    range X = 0..200;
    
    tuple Task {
        key string id;
        int duration;
    }
    
    tuple TaskExecution {
        Task task;
        int execution;
    }
    
    tuple TaskExecutionIndex {
        TaskExecution task_execution;
        int index;
    }
    
    {Task} J = {<"j0",2>, <"j1",3>};
    {TaskExecution} A = {<j,x> | j in J, x in X};
    {TaskExecutionIndex} AP = {<a,p> | a in A, p in 0..a.task.duration-1};
    
    
    dvar int task_executions[j in J] in T;
    dvar int active[ap in AP] in T;
    
    //1. dexpr int active_task[j in J, t in T] = count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t);
    //2. dexpr int active_task[j in J, t in T] = sum(x in X, p in 0..j.duration-1) (active[<<j,x>,p>] == t && x < task_executions[j]);
    
    dexpr int load[t in T] = sum(j in J) active_task[j, t];
    
    subject to{
    
        forall(t in T)
            c1: load[t] == 1;
            
            
    //    c2: active[<<<"j0",2>,0>,0>] == 0;
    //    c3: active[<<<"j0",2>,0>,1>] == 1;
    //    c4: active[<<<"j1",3>,0>,0>] == 0;
    //    c5: active[<<<"j1",3>,0>,1>] == 3;
    //    c6: active[<<<"j1",3>,0>,2>] == 4;
    //    
    //    c7: task_executions[<"j0",2>] == 1;
    //    c8: task_executions[<"j1",3>] == 1;
    }
    

    Note that the task executions range now in X=0..200 and T ranges in 0..400. These numbers are similar to the instance of the problem I'm trying to solve, and from which I derived this minimal working example to show you this issue.

    In this case, the alternative 1 for the definition of active_task leads to a model with 401 constraints (basically one for each t in T). If it would work, I think it would lead to a very efficient model, where the number of constraints is linear with respect to the size of T.

    The second alternative you proposed instead, leads to a model of over 1 million constraints that CP Optimizier is barely able to load (and solve)! I guess, but that's only speculation since I'm not an expert about CP, that this is a common problem with CP when one has many binary variables (whose domain then it's only true-false): in this case the propagation and domain-reduction is quite inefficient. From this point of view, the first alternative with count/all would be much more preferable, but I'm not sure if it's meant to really work with variable ranges. If not then, why does it compile and has such an inconsistent behavior?

     

    Regards,

    Stefano

    Hello Stefano,

    David is right: dvars are not allowed in a range (0..dvar), neither in any filter.
    And OPL should have raised an error.
    For example, such expression - which states the same than the one that you wrote - will not work and will raise an error:

      count(all(x in 0..0, p in 0..j.duration-1 : x < task_executions[j]) active[<<j,x>,p>], t);
    

    Despite the fact that you didn't get any error and, in some case, you got the right result, you cannot expect a right behaviour by using such kind of expression.
    Using sum of binaries is the right way to write your model.

    Regards,

    Chris.
     

  • davidoff
    davidoff
    51 Posts

    Re: Strange solver behavior using dexprs with count/all syntax and tuples

    ‏2014-01-25T09:25:33Z  

    Hi Stefano

    the line

    dexpr int active_task[j in J, t in T] = count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t);
    

    is completely weird for me, and I do not understand how this usage of the "all" keyword is allowed with OPL (I'm running with the 12.5). Here , task_executions is a variable so you use an all keyword to collect some index x. The documentation does not allow such usage , as far as I read it correctly.

    Having said that, this model should also create another exception since the active variable active[<<j,x>,p>] would be then accessed with possible x>0, while you created the {TaskExecution} collection with x in 0..0

    To summarize : this model should even not compile, and surely crashes at runtime. Since it is not the case, my explanation is maybe completely wrong too :-)

    David

  • s.st1led
    s.st1led
    16 Posts

    Re: Strange solver behavior using dexprs with count/all syntax and tuples

    ‏2014-01-25T13:36:08Z  
    • davidoff
    • ‏2014-01-25T09:25:33Z

    Hi Stefano

    the line

    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">dexpr int active_task[j in J, t in T] = count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t); </pre>

    is completely weird for me, and I do not understand how this usage of the "all" keyword is allowed with OPL (I'm running with the 12.5). Here , task_executions is a variable so you use an all keyword to collect some index x. The documentation does not allow such usage , as far as I read it correctly.

    Having said that, this model should also create another exception since the active variable active[<<j,x>,p>] would be then accessed with possible x>0, while you created the {TaskExecution} collection with x in 0..0

    To summarize : this model should even not compile, and surely crashes at runtime. Since it is not the case, my explanation is maybe completely wrong too :-)

    David

    Thank you for your answer David! Looks like I opened a Pandora's box then.

    With respect to the first problem that you said, it really looks like the all syntax supports ranges defined by variable values. This even simpler example compiles and executes fine for instance:

    using CP;
    
    range T = 0..4;
    range J = 0..3;
    range AP = 0..5;
    
    dvar int task_executions[j in J] in T;
    dvar int active[ap in AP] in T;
    
    dexpr int active_task[j in J, t in T] = count(all(x in 0..task_executions[j]-1) active[x], t);
    
    subject to{
    
    task_executions[0] == 0;
    task_executions[1] == 1;
    task_executions[2] == 2;
    task_executions[3] == 3;
    
    active[0] == 0;
    active[1] == 1;
    active[2] == 2;
    active[3] == 3;
    active[4] == 4;
    
    }
    

    At least, I don't have any problems with the 12.6, but as far as I remember the example in my first post was working with 12.5 as well (both x64).

    You are right about the second potential error:

    "the active variable active[<<j,x>,p>] would be then accessed with possible x>0, while you created the {TaskExecution} collection with x in 0..0". 

    This could happen if task_executions might have for some j a value greater than 1 (and it could since it's defined in T=0..4), but just suppose that task_executions and x in the {TaskExecutions} set have the same domain, this example still leads to the unexpected behavior.

    using CP;
    
    range T = 0..4;
    range X = 0..1;
    
    tuple Task {
        key string id;
        int duration;
    }
    
    tuple TaskExecution {
        Task task;
        int execution;
    }
    
    tuple TaskExecutionIndex {
        TaskExecution task_execution;
        int index;
    }
    
    {Task} J = {<"j0",2>, <"j1",3>};
    {TaskExecution} A = {<j,x> | j in J, x in X};
    {TaskExecutionIndex} AP = {<a,p> | a in A, p in 0..a.task.duration-1};
    
    
    dvar int task_executions[j in J] in X;
    dvar int active[ap in AP] in T;
    
    dexpr int active_task[j in J, t in T] = count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t);
    dexpr int load[t in T] = sum(j in J) active_task[j, t];
    
    subject to{
    
        forall(t in T)
            c1: load[t] <= 1;
            
            
        c2: active[<<<"j0",2>,0>,0>] == 0;
        c3: active[<<<"j0",2>,0>,1>] == 1;
        c4: active[<<<"j1",3>,0>,0>] == 0;
        c5: active[<<<"j1",3>,0>,1>] == 3;
        c6: active[<<<"j1",3>,0>,2>] == 4;
        
        c7: task_executions[<"j0",2>] == 1;
        c8: task_executions[<"j1",3>] == 1;
    }
    

    What now? :)

    Updated on 2014-01-25T13:40:05Z at 2014-01-25T13:40:05Z by s.st1led
  • AlexFleischer
    AlexFleischer
    75 Posts

    Re: Strange solver behavior using dexprs with count/all syntax and tuples

    ‏2014-01-25T16:19:47Z  
    • s.st1led
    • ‏2014-01-25T13:36:08Z

    Thank you for your answer David! Looks like I opened a Pandora's box then.

    With respect to the first problem that you said, it really looks like the all syntax supports ranges defined by variable values. This even simpler example compiles and executes fine for instance:

    <pre class="javascript dw" data-editor-lang="js" data-pbcklang="javascript" dir="ltr">using CP; range T = 0..4; range J = 0..3; range AP = 0..5; dvar int task_executions[j in J] in T; dvar int active[ap in AP] in T; dexpr int active_task[j in J, t in T] = count(all(x in 0..task_executions[j]-1) active[x], t); subject to{ task_executions[0] == 0; task_executions[1] == 1; task_executions[2] == 2; task_executions[3] == 3; active[0] == 0; active[1] == 1; active[2] == 2; active[3] == 3; active[4] == 4; } </pre>

    At least, I don't have any problems with the 12.6, but as far as I remember the example in my first post was working with 12.5 as well (both x64).

    You are right about the second potential error:

    "the active variable active[<<j,x>,p>] would be then accessed with possible x>0, while you created the {TaskExecution} collection with x in 0..0". 

    This could happen if task_executions might have for some j a value greater than 1 (and it could since it's defined in T=0..4), but just suppose that task_executions and x in the {TaskExecutions} set have the same domain, this example still leads to the unexpected behavior.

    <pre class="javascript dw" data-editor-lang="js" data-pbcklang="javascript" dir="ltr">using CP; range T = 0..4; range X = 0..1; tuple Task { key string id; int duration; } tuple TaskExecution { Task task; int execution; } tuple TaskExecutionIndex { TaskExecution task_execution; int index; } {Task} J = {<"j0",2>, <"j1",3>}; {TaskExecution} A = {<j,x> | j in J, x in X}; {TaskExecutionIndex} AP = {<a,p> | a in A, p in 0..a.task.duration-1}; dvar int task_executions[j in J] in X; dvar int active[ap in AP] in T; dexpr int active_task[j in J, t in T] = count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t); dexpr int load[t in T] = sum(j in J) active_task[j, t]; subject to{ forall(t in T) c1: load[t] <= 1; c2: active[<<<"j0",2>,0>,0>] == 0; c3: active[<<<"j0",2>,0>,1>] == 1; c4: active[<<<"j1",3>,0>,0>] == 0; c5: active[<<<"j1",3>,0>,1>] == 3; c6: active[<<<"j1",3>,0>,2>] == 4; c7: task_executions[<"j0",2>] == 1; c8: task_executions[<"j1",3>] == 1; } </pre>

    What now? :)

    Hi,

    if you change dexpr into dvar, do you still have the strange behaviour ?

    You could change

    dexpr int active_task[j in J, t in T] = count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t);
    dexpr int load[t in T] = sum(j in J) active_task[j, t];

     

    into

    dvar int active_task[j in J, t in T];
    dvar int load[t in T];


    subject to{
     
      forall(j in J, t in T)  active_task[j, t] == count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t);
      forall(t in T)  load[t] == sum(j in J) active_task[j, t];

     

    regards

  • s.st1led
    s.st1led
    16 Posts

    Re: Strange solver behavior using dexprs with count/all syntax and tuples

    ‏2014-01-26T00:34:57Z  

    Hi,

    if you change dexpr into dvar, do you still have the strange behaviour ?

    You could change

    dexpr int active_task[j in J, t in T] = count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t);
    dexpr int load[t in T] = sum(j in J) active_task[j, t];

     

    into

    dvar int active_task[j in J, t in T];
    dvar int load[t in T];


    subject to{
     
      forall(j in J, t in T)  active_task[j, t] == count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t);
      forall(t in T)  load[t] == sum(j in J) active_task[j, t];

     

    regards

    That's even more weird: if I change the dexpr into a dvar plus an equality constraint, CP still says the problem is feasible but now the load variable gets all zeros as values in the solution:

    using CP;
    
    range T = 0..4;
    
    tuple Task {
        key string id;
        int duration;
    }
    
    tuple TaskExecution {
        Task task;
        int execution;
    }
    
    tuple TaskExecutionIndex {
        TaskExecution task_execution;
        int index;
    }
    
    {Task} J = {<"j0",2>, <"j1",3>};
    {TaskExecution} A = {<j,x> | j in J, x in 0..0};
    {TaskExecutionIndex} AP = {<a,p> | a in A, p in 0..a.task.duration-1};
    
    
    dvar int task_executions[j in J] in T;
    dvar int active[ap in AP] in T;
    
    dexpr int active_task[j in J, t in T] = count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t);
    dvar int load[t in T];
    
    subject to{
    
        forall(t in T)
            c1: load[t] <= 1;
            
            
        c2: active[<<<"j0",2>,0>,0>] == 0;
        c3: active[<<<"j0",2>,0>,1>] == 1;
        c4: active[<<<"j1",3>,0>,0>] == 0;
        c5: active[<<<"j1",3>,0>,1>] == 3;
        c6: active[<<<"j1",3>,0>,2>] == 4;
        
        c7: task_executions[<"j0",2>] == 1;
        c8: task_executions[<"j1",3>] == 1;
        
        forall(t in T)
              c9: load[t] == sum(j in J) active_task[j, t]; // The solution for load is = [0, 0, 0, 0] while the model should be unfeasible because with these assignments it should be [2, 1, 0, 1, 1]
    }
    

    Same thing as before, if I remove c2-c8 and replace c1 with load[t] == 1 the problem is still deemed unfeasible.

     

    Regards,

    Stefano

  • AlexFleischer
    AlexFleischer
    75 Posts

    Re: Strange solver behavior using dexprs with count/all syntax and tuples

    ‏2014-01-26T09:33:55Z  
    • s.st1led
    • ‏2014-01-26T00:34:57Z

    That's even more weird: if I change the dexpr into a dvar plus an equality constraint, CP still says the problem is feasible but now the load variable gets all zeros as values in the solution:

    <pre class="html dw" data-editor-lang="js" data-pbcklang="html" dir="ltr">using CP; range T = 0..4; tuple Task { key string id; int duration; } tuple TaskExecution { Task task; int execution; } tuple TaskExecutionIndex { TaskExecution task_execution; int index; } {Task} J = {<"j0",2>, <"j1",3>}; {TaskExecution} A = {<j,x> | j in J, x in 0..0}; {TaskExecutionIndex} AP = {<a,p> | a in A, p in 0..a.task.duration-1}; dvar int task_executions[j in J] in T; dvar int active[ap in AP] in T; dexpr int active_task[j in J, t in T] = count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t); dvar int load[t in T]; subject to{ forall(t in T) c1: load[t] <= 1; c2: active[<<<"j0",2>,0>,0>] == 0; c3: active[<<<"j0",2>,0>,1>] == 1; c4: active[<<<"j1",3>,0>,0>] == 0; c5: active[<<<"j1",3>,0>,1>] == 3; c6: active[<<<"j1",3>,0>,2>] == 4; c7: task_executions[<"j0",2>] == 1; c8: task_executions[<"j1",3>] == 1; forall(t in T) c9: load[t] == sum(j in J) active_task[j, t]; // The solution for load is = [0, 0, 0, 0] while the model should be unfeasible because with these assignments it should be [2, 1, 0, 1, 1] } </pre>

    Same thing as before, if I remove c2-c8 and replace c1 with load[t] == 1 the problem is still deemed unfeasible.

     

    Regards,

    Stefano

    Hi

    and if you replace

    forall(j in J, t in T)  active_task[j, t] == count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t);

    by

    forall(j in J, t in T)  active_task[j, t] == (sum(x in 0..0,p in 0..j.duration-1)
      ((p<=task_executions[j]-1) &&(active[<<j,x>,p>]==t)));

    ?

  • s.st1led
    s.st1led
    16 Posts

    Re: Strange solver behavior using dexprs with count/all syntax and tuples

    ‏2014-01-26T12:08:20Z  

    Hi

    and if you replace

    forall(j in J, t in T)  active_task[j, t] == count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t);

    by

    forall(j in J, t in T)  active_task[j, t] == (sum(x in 0..0,p in 0..j.duration-1)
      ((p<=task_executions[j]-1) &&(active[<<j,x>,p>]==t)));

    ?

    Thank you, if I replace the count/all by the sum of binary variables, then the model correctly states that the first problem is unfeasible, and the second is feasible returning a solution. From the correctness point of view there's no problem here, and I would be more than happy to use this solution you proposed.

    However, I'm afraid that defining active_task as a sum of binary variables is very inefficient. Consider this final model:

    using CP;
    range T = 0..400;
    range X = 0..200;
    
    tuple Task {
        key string id;
        int duration;
    }
    
    tuple TaskExecution {
        Task task;
        int execution;
    }
    
    tuple TaskExecutionIndex {
        TaskExecution task_execution;
        int index;
    }
    
    {Task} J = {<"j0",2>, <"j1",3>};
    {TaskExecution} A = {<j,x> | j in J, x in X};
    {TaskExecutionIndex} AP = {<a,p> | a in A, p in 0..a.task.duration-1};
    
    
    dvar int task_executions[j in J] in T;
    dvar int active[ap in AP] in T;
    
    //1. dexpr int active_task[j in J, t in T] = count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t);
    //2. dexpr int active_task[j in J, t in T] = sum(x in X, p in 0..j.duration-1) (active[<<j,x>,p>] == t && x < task_executions[j]);
    
    dexpr int load[t in T] = sum(j in J) active_task[j, t];
    
    subject to{
    
        forall(t in T)
            c1: load[t] == 1;
            
            
    //    c2: active[<<<"j0",2>,0>,0>] == 0;
    //    c3: active[<<<"j0",2>,0>,1>] == 1;
    //    c4: active[<<<"j1",3>,0>,0>] == 0;
    //    c5: active[<<<"j1",3>,0>,1>] == 3;
    //    c6: active[<<<"j1",3>,0>,2>] == 4;
    //    
    //    c7: task_executions[<"j0",2>] == 1;
    //    c8: task_executions[<"j1",3>] == 1;
    }
    

    Note that the task executions range now in X=0..200 and T ranges in 0..400. These numbers are similar to the instance of the problem I'm trying to solve, and from which I derived this minimal working example to show you this issue.

    In this case, the alternative 1 for the definition of active_task leads to a model with 401 constraints (basically one for each t in T). If it would work, I think it would lead to a very efficient model, where the number of constraints is linear with respect to the size of T.

    The second alternative you proposed instead, leads to a model of over 1 million constraints that CP Optimizier is barely able to load (and solve)! I guess, but that's only speculation since I'm not an expert about CP, that this is a common problem with CP when one has many binary variables (whose domain then it's only true-false): in this case the propagation and domain-reduction is quite inefficient. From this point of view, the first alternative with count/all would be much more preferable, but I'm not sure if it's meant to really work with variable ranges. If not then, why does it compile and has such an inconsistent behavior?

     

    Regards,

    Stefano

    Updated on 2014-01-26T12:11:00Z at 2014-01-26T12:11:00Z by s.st1led
  • ChrisBr
    ChrisBr
    40 Posts

    Re: Strange solver behavior using dexprs with count/all syntax and tuples

    ‏2014-01-27T17:32:14Z  
    • s.st1led
    • ‏2014-01-26T12:08:20Z

    Thank you, if I replace the count/all by the sum of binary variables, then the model correctly states that the first problem is unfeasible, and the second is feasible returning a solution. From the correctness point of view there's no problem here, and I would be more than happy to use this solution you proposed.

    However, I'm afraid that defining active_task as a sum of binary variables is very inefficient. Consider this final model:

    <pre class="html dw" data-editor-lang="js" data-pbcklang="html" dir="ltr">using CP; range T = 0..400; range X = 0..200; tuple Task { key string id; int duration; } tuple TaskExecution { Task task; int execution; } tuple TaskExecutionIndex { TaskExecution task_execution; int index; } {Task} J = {<"j0",2>, <"j1",3>}; {TaskExecution} A = {<j,x> | j in J, x in X}; {TaskExecutionIndex} AP = {<a,p> | a in A, p in 0..a.task.duration-1}; dvar int task_executions[j in J] in T; dvar int active[ap in AP] in T; //1. dexpr int active_task[j in J, t in T] = count(all(x in 0..task_executions[j]-1, p in 0..j.duration-1) active[<<j,x>,p>], t); //2. dexpr int active_task[j in J, t in T] = sum(x in X, p in 0..j.duration-1) (active[<<j,x>,p>] == t && x < task_executions[j]); dexpr int load[t in T] = sum(j in J) active_task[j, t]; subject to{ forall(t in T) c1: load[t] == 1; // c2: active[<<<"j0",2>,0>,0>] == 0; // c3: active[<<<"j0",2>,0>,1>] == 1; // c4: active[<<<"j1",3>,0>,0>] == 0; // c5: active[<<<"j1",3>,0>,1>] == 3; // c6: active[<<<"j1",3>,0>,2>] == 4; // // c7: task_executions[<"j0",2>] == 1; // c8: task_executions[<"j1",3>] == 1; } </pre>

    Note that the task executions range now in X=0..200 and T ranges in 0..400. These numbers are similar to the instance of the problem I'm trying to solve, and from which I derived this minimal working example to show you this issue.

    In this case, the alternative 1 for the definition of active_task leads to a model with 401 constraints (basically one for each t in T). If it would work, I think it would lead to a very efficient model, where the number of constraints is linear with respect to the size of T.

    The second alternative you proposed instead, leads to a model of over 1 million constraints that CP Optimizier is barely able to load (and solve)! I guess, but that's only speculation since I'm not an expert about CP, that this is a common problem with CP when one has many binary variables (whose domain then it's only true-false): in this case the propagation and domain-reduction is quite inefficient. From this point of view, the first alternative with count/all would be much more preferable, but I'm not sure if it's meant to really work with variable ranges. If not then, why does it compile and has such an inconsistent behavior?

     

    Regards,

    Stefano

    Hello Stefano,

    David is right: dvars are not allowed in a range (0..dvar), neither in any filter.
    And OPL should have raised an error.
    For example, such expression - which states the same than the one that you wrote - will not work and will raise an error:

      count(all(x in 0..0, p in 0..j.duration-1 : x < task_executions[j]) active[<<j,x>,p>], t);
    

    Despite the fact that you didn't get any error and, in some case, you got the right result, you cannot expect a right behaviour by using such kind of expression.
    Using sum of binaries is the right way to write your model.

    Regards,

    Chris.
     

  • s.st1led
    s.st1led
    16 Posts

    Re: Strange solver behavior using dexprs with count/all syntax and tuples

    ‏2014-01-28T08:45:09Z  
    • ChrisBr
    • ‏2014-01-27T17:32:14Z

    Hello Stefano,

    David is right: dvars are not allowed in a range (0..dvar), neither in any filter.
    And OPL should have raised an error.
    For example, such expression - which states the same than the one that you wrote - will not work and will raise an error:

    <pre class="html dw" data-editor-lang="js" data-pbcklang="html" dir="ltr"> count(all(x in 0..0, p in 0..j.duration-1 : x < task_executions[j]) active[<<j,x>,p>], t); </pre>

    Despite the fact that you didn't get any error and, in some case, you got the right result, you cannot expect a right behaviour by using such kind of expression.
    Using sum of binaries is the right way to write your model.

    Regards,

    Chris.
     

    I see. Indeed I know that variables aren't allowed in scopes such as after the colon, but since OPL wasn't raising a syntax error in this case I thought all was somehow different.

    Many thanks for your support!

     

    Regards,

    Stefano

  • davidoff
    davidoff
    51 Posts

    Re: Strange solver behavior using dexprs with count/all syntax and tuples

    ‏2014-01-29T20:33:47Z  
    • s.st1led
    • ‏2014-01-28T08:45:09Z

    I see. Indeed I know that variables aren't allowed in scopes such as after the colon, but since OPL wasn't raising a syntax error in this case I thought all was somehow different.

    Many thanks for your support!

     

    Regards,

    Stefano

    Looking at your model, it seems to me that you are trying roughly to count the occurences of tasks at any time points of a given horizon.

    Do you know that the CP scheduling API could let you model this with much more performance through intervals and cumulative functions ? Namely without discretizing time .

    David

  • s.st1led
    s.st1led
    16 Posts

    Re: Strange solver behavior using dexprs with count/all syntax and tuples

    ‏2014-01-29T20:58:29Z  
    • davidoff
    • ‏2014-01-29T20:33:47Z

    Looking at your model, it seems to me that you are trying roughly to count the occurences of tasks at any time points of a given horizon.

    Do you know that the CP scheduling API could let you model this with much more performance through intervals and cumulative functions ? Namely without discretizing time .

    David

    Hi David, yes I am aware of the OPL scheduling functions, as they were my first try to model the problem from which I created this minimal working example. However, my problem also involves many other complications, such as each task is defined with a static priority and should get preempted whenever a higher priority task is ready and there are not enough resources for it to be run. I was never able to define such a constraint, and therefore I gave up with the scheduling functions, as things were starting getting too complicated: (ref: https://www.ibm.com/developerworks/community/forums/html/topic?id=77777777-0000-0000-0000-000014796693)

    However, very recently I'm starting to get help on this side from some experts, so I'm actually also coming back to the OPL scheduling functions.

     

    Regards,

    Stefano