Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.

 View Only

  • 1.  noOverlap constraint for Tuple key int id

    Posted Wed April 26, 2023 11:40 PM

    I'm using CP Optimizer for an RCPSP. I was wondering if there exists a simple way to impose a noOverlap constraint for determined tuples id. For example, avoid an overlap between Tasks with id 1 and Tasks with id 2. Is that possible?

    using CP;
int NbTasks = ...;
int NbRsrcs = ...;
range RsrcIds = 0..NbRsrcs-1; 
int Capacity[r in RsrcIds] = ...;

tuple Task {
  key int id;
  int     pt;
  int     dmds[RsrcIds];
  {int}   succs; 
}

{Task} Tasks = ...;

dvar interval itvs[t in Tasks]  size t.pt;

cumulFunction rsrcUsage[r in RsrcIds] = 
  sum (t in Tasks: t.dmds[r]>0) pulse(itvs[t], t.dmds[r]);

minimize max(t in Tasks) endOf(itvs[t]);

subject to {  
  forall (r in RsrcIds)
    rsrcUsage[r] <= Capacity[r];
  forall (t1 in Tasks, t2id in t1.succs)
    endBeforeStart(itvs[t1], itvs[<t2id>]);    
}


    ------------------------------
    Francisco Yuraszeck
    Yuraszeck
    ------------------------------


  • 2.  RE: noOverlap constraint for Tuple key int id

    Posted Thu April 27, 2023 10:08 AM
    Edited by PhR Thu April 27, 2023 10:11 AM

    Use could use state functions for that, see https://www.ibm.com/docs/en/icos/22.1.1?topic=scheduling-state-functions

    You can declare a single state function

    stateFunction typeExclusionFn

    and then create the exclusion between tasks sets by using the id of each task intervalVar and the constraint 

    alwaysEqual(typeExclusionFn, intervalVar, id)

    for each task. 

    This provides a more global view that many nooverlap constraints. It behaves as a single resource that can be used by only one type of task at the same time.

    Other classes of relations can be defined thanks state functions.

    Regards

    Philippe



    ------------------------------
    Philippe Refalo
    IBM ILOG CP Optimizer
    ------------------------------

    Original Message


  • 3.  RE: noOverlap constraint for Tuple key int id

    Posted Thu April 27, 2023 12:54 PM

    Thank you Philippe for your answer.

    But I still have doubts about how to avoid an overlap between determined Tasks, for instance, Tasks with id 1 and Tasks with id 2.

    Given your answer, I was thinking of adding a new constraint something like:

      forall (t in Tasks)  
  	alwaysEqual(typeExclusionFn, itvs[t], t.id);

    But I am not sure how to impose that for certain values of the id field the itvs variable can not overlap. Indeed, I would like to avoid overlap for tasks with id in the range of 1 to N (with N < NbTasks).

    Thanks in advance




    ------------------------------
    Francisco Yuraszeck
    Yuraszeck
    ------------------------------

    Original Message


  • 4.  RE: noOverlap constraint for Tuple key int id

    Posted Thu April 27, 2023 09:12 PM
    Edited by Scott Dunn Thu April 27, 2023 09:15 PM

    Yes, you can impose a noOverlap constraint between specific tasks in the CP Optimizer. You can add an additional constraint to your existing model, which ensures that certain pairs of tasks do not overlap. In your example, you want to avoid an overlap between tasks with id 1 and tasks with id 2.

    You can achieve this by adding the following constraint to the `subject to` block in your model:

    ```cplex
    forall (t1 in Tasks, t2 in Tasks: t1.id == 1 && t2.id == 2)
        noOverlap(itvs[t1], itvs[t2]);
    ```

    This constraint iterates through all the tasks and ensures that if a task has an id of 1, it will not overlap with any tasks having an id of 2.

    Here's the updated model with the added constraint:

    ```cplex
    using CP;
    int NbTasks = ...;
    int NbRsrcs = ...;
    range RsrcIds = 0..NbRsrcs-1; 
    int Capacity[r in RsrcIds] = ...;

    tuple Task {
      key int id;
      int     pt;
      int     dmds[RsrcIds];
      {int}   succs; 
    }

    {Task} Tasks = ...;

    dvar interval itvs[t in Tasks]  size t.pt;

    cumulFunction rsrcUsage[r in RsrcIds] = 
      sum (t in Tasks: t.dmds[r]>0) pulse(itvs[t], t.dmds[r]);

    minimize max(t in Tasks) endOf(itvs[t]);

    subject to {  
      forall (r in RsrcIds)
        rsrcUsage[r] <= Capacity[r];
      forall (t1 in Tasks, t2id in t1.succs)
        endBeforeStart(itvs[t1], itvs[<t2id>]);
      // Add noOverlap constraint for specific task ids
      forall (t1 in Tasks, t2 in Tasks: t1.id == 1 && t2.id == 2)
        noOverlap(itvs[t1], itvs[t2]);
    }
    ```

    Now, the model will ensure that tasks with id 1 do not overlap with tasks with id 2. You can extend this constraint to include other task pairs as needed.



    ------------------------------
    Scott Dunn
    ------------------------------

    Original Message


  • 5.  RE: noOverlap constraint for Tuple key int id

    Posted Fri April 28, 2023 09:55 AM

    Thank you Scott for taking the time to answer my question.

    I followed your advice but now I have a warning at the noOverlap constraint. 

    The warning (translated from Spanish to English) says: "The function noOverlap(dvar interval, dvar interval) does not exist"



    ------------------------------
    Francisco Yuraszeck
    Yuraszeck
    ------------------------------

    Original Message


  • 6.  RE: noOverlap constraint for Tuple key int id

    Posted Fri April 28, 2023 03:53 PM
    Edited by Scott Dunn Fri April 28, 2023 03:58 PM

    Apologies. It seems there was a misunderstanding. In the CP Optimizer, there is no direct `noOverlap` constraint that takes two interval variables as input. Instead, you should use the state function approach as I previously described. Here's a modified version of the model that avoids overlaps between tasks with specific IDs:

    using CP;
    int NbTasks = ...;
    int NbRsrcs = ...;
    range RsrcIds = 0..NbRsrcs-1;
    int Capacity[r in RsrcIds] = ...;

    tuple Task {
      key int id;
      int     pt;
      int     dmds[RsrcIds];
      {int}   succs;
    }

    {Task} Tasks = ...;

    dvar interval itvs[t in Tasks] size t.pt;

    cumulFunction rsrcUsage[r in RsrcIds] =
      sum (t in Tasks: t.dmds[r]>0) pulse(itvs[t], t.dmds[r]);

    minimize max(t in Tasks) endOf(itvs[t]);

    // Add a state function
    stateFunction typeExclusionFn;

    // Define tags for tasks you want to avoid overlapping
    int Tag1 = 1;
    int Tag2 = 2;

    subject to {
      forall (r in RsrcIds)
        rsrcUsage[r] <= Capacity[r];
      forall (t1 in Tasks, t2id in t1.succs)
        endBeforeStart(itvs[t1], itvs[<t2id>]);
      // Add alwaysEqual constraints to prevent overlaps between tasks with specific IDs
      forall (t in Tasks)
        if (t.id == 1)
          alwaysEqual(typeExclusionFn, itvs[t], Tag1);
        else if (t.id == 2)
          alwaysEqual(typeExclusionFn, itvs[t], Tag2);
    }



    By using the state function `typeExclusionFn` and the `alwaysEqual` constraints, this model will ensure that tasks with ID 1 and tasks with ID 2 do not overlap.



    ------------------------------
    Scott Dunn
    ------------------------------

    Original Message


  • 7.  RE: noOverlap constraint for Tuple key int id

    Posted Fri April 28, 2023 04:10 AM
    Edited by PhR Fri April 28, 2023 04:11 AM

    If one need to constraint that a set of tasks T = { T1, ..., Tn } cannot overlap each other, the constraint nooverlap([T1,...,Tn]) does the job.

    If the need is to avoid that each task (or interval var) from a set T = { T1, ..., Tn } does not overlap any task from a set Q = { Q1,..., Qm } while tasks Ti could overlap each other (same for Qi) you need to decide for different tags (integer values) : TagT for set T and TagQ for set Q and use a state function :

    stateFunction typeExclusionFn

    Then, the constraint

    alwaysEqual(typeExclusionFn, T1, TagT)  (1)

    constrain the state function to take value TagT over the interval of T1.

    Adding the constraint 

    alwaysEqual(typeExclusionFn, Q1, TagQ)  (2)

    constrain the state function to take value TagQ over the interval of Q1 

    The state function cannot be fixed to two different values. Since TagT and TagQ are different, the intervals of T1 and Q1 cannot overlap.
    Adding (1) for each Ti and (2) for each Qi expresses the desired constraint. So, you need to group your taks and choose a different tag for each group. 

    It is also possible to use n * m nooverlap constraints but, in general, this achieve a weaker domain reduction than the use of a single state function instead.

    Philippe



    ------------------------------
    Philippe Refalo
    IBM ILOG CP Optimizer
    ------------------------------

    Original Message


  • 8.  RE: noOverlap constraint for Tuple key int id

    Posted Fri April 28, 2023 10:13 AM

    Thank you again Philippe.

    According to your answer, I need only the noOverlap constraint (a constraint that a set of tasks id cannot overlap each other).

    Remembering, I have the following tuple:

    tuple Task {
  key int id;
  int     pt;
  int     dmds[RsrcIds];
  {int}   succs; 
}


    And then, I added the following constraint:

    nooverlap([Tasks.id==1,Tasks.id==2]);


    To avoid an overlap between Task with id 1 and Task with id 2. But, does not seem to work. 

    Could you please tell me what is wrong with the constraint?

    Thank you.



    ------------------------------
    Francisco Yuraszeck
    Yuraszeck
    ------------------------------

    Original Message


  • 9.  RE: noOverlap constraint for Tuple key int id

    Posted Fri April 28, 2023 12:04 PM

    To use a noOverlap constraint, you have to define a sequence variable. A sequence variable groups a set of interval variable to define a total order over them. You probably need to add a field into the task descriptor to define the group the variable belongs to, with the idea that interval variables of the same group cannot overlap :

    tuple Task {
      key int id;
      int     group
      int     pt;
      int     dmds[RsrcIds];
      {int}   succs; 
    }

    Then you define a sequence variable for each group :

    dvar sequence groupSequence[g in Groups] in all(<id, group, ...> in Tasks : group == g) itvs[<id, g, ...>];

    assuming that Groups is the range of all tasks groups. 

    Then for each group you can add the no-overlap constraint:

    forall(g in Groups) noOverlap(groupSequence[g]);

    This is of course a sketch of code, you need to adapt it. 



    ------------------------------
    Philippe Refalo
    IBM ILOG CP Optimizer
    ------------------------------

    Original Message


Related Content