Decision Optimization

 View Only
  • 1.  Tracking Max/Min of Cumul Function within Fixed intervals

    Posted Thu December 16, 2021 03:23 PM
    Edited by Louis Luo Thu December 16, 2021 03:25 PM
    Hi,

    In CP Optimizer, I was wondering is there a way to track the maximum or minimum of a cumulative function within some fixed interval that is a subset of cumul function's domain?

    For instance, say I have a cumul function representing one big resource from time 0 to time 100, and I want to add, to an objective function, two linear costs associated with the minimum/maximum value of this cumulative function from time intervals [10, 50] and [50, 80], respectively. 

    I am aware that I can track the max of a cumul function (f) over its entire domain by the simple expression "f <= x", where x is an integer variable, and similarly the minimum. For a subset of the domain, I see on the documentation [1] that perhaps I can do this with "AlwaysIn" constraint, but I found that its arguments "h_min" and "h_max" cannot be (integer) variables during implementation.

    One idea is that perhaps I can decompose single resource into separate ones segmented by the start and end times of these fixed intervals (e.g. [0, 10], [10, 50], [50, 80], [80, 100]), but that would involve using "Alternative" constraint and creating more interval variables, which I am reluctant to do. Is there a better way to accomplish this?

    [1] https://www.ibm.com/docs/en/icos/20.1.0?topic=concepts-cumul-functions-in-cp-optimizer

    Thanks,
    Louis

    ------------------------------
    Louis Luo
    ------------------------------


  • 2.  RE: Tracking Max/Min of Cumul Function within Fixed intervals

    Posted Fri December 17, 2021 04:30 AM
    Hi,

    you can add cumuls.

    For instance,

    using CP;
    
    range r=1..3;
    
    dvar interval itvs[i in 1..3] in i..i+5 size 5;
    
    
    // 3 simple cumuls
    cumulFunction  ci[i in r]=pulse(itvs[i],i);
    cumulFunction ci4=pulse(0,10,100);
    
    // sum of those 3 cumuls
    cumulFunction sumc=sum(i in r) ci[i];
    cumulFunction sumc2=ci[1]+ci[3]-ci[2]+ci4;
    
    subject to
    {
      sumc<=10;
      sumc2<=1000;
    }​


    works fine

    Using this you could manage with what you need



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



  • 3.  RE: Tracking Max/Min of Cumul Function within Fixed intervals

    Posted Fri December 17, 2021 02:39 PM
    Edited by Louis Luo Sat December 18, 2021 01:00 AM
    Hi Alex,

    Thank you for your response. I am not sure if I can simply use the inequality as you have suggested, because the inequality implies the maximum/minimum over the entire time horizon of the cumul function, but I only want the max/min over some subset of the time horizon (i.e. local max/min).

    I would like to append one more (complicating) details about the problem structure (that hopefully clarifies my intention):
    • the start time of the jobs can be anywhere over the domain of the cumulative function of the sole resource
    Also, to avoid confusion, I will refer to the fixed intervals of time as "zones" (e.g [10, 50] in the previous post). I will illustrate the problem in an example solution, where I would like to keep track of the max/min of the cumul function within a "zone".

    Then, since the interval variables (representing jobs) can start anywhere in the domain of the cumul function, I found that I could not track the maximum or minimum of the cumul function as I would not know which jobs falls into the zone or outside of the zone.

    For instance, for the following solution (where z denotes a zone and the resource has capacity of 6):
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 Time Horizon id
    - - - - z z z z z z z - - - Time "Zone" Locations
    [ J1 ] [ J2 ] [ J3 ] Job Intervals (of fixed size)
    [ J4 ]
    2 2 2 0 4 6 6 6 6 2 2 0 0 0 Cumul Function Value

    Ideally, I would like to penalize any capacity of the resource not used to full over the time "zone". In this solution, I will penalize t = {5, 10, 11} only, as the "zone" starts at t = 5 and ends at t = 11. One approximation I can compromise with is to only penalize (the total resource capacity - maximum usage over the time zone), which may be simpler, hence motivating my original question.

    Does this make sense?


    ------------------------------
    Louis Luo
    ------------------------------



  • 4.  RE: Tracking Max/Min of Cumul Function within Fixed intervals

    Posted Sun December 19, 2021 03:17 PM
    Going on with sum of cumuls, I would write

    using CP;
    
    int offset=100;
    int s=10;
    int e=50;
    dvar int+ x in 0..1000;
    
    dvar interval itvs[1..3] in 0..1000 size 10;
    cumulFunction c=sum(i in 1..3) pulse(itvs[i],1);
    cumulFunction c2=c+pulse(s,e,offset);
    
    minimize x;
    
    subject to
    {
      c<=1;
     c2<=offset+x;
    }​


    where the goal is to minimize what is between s=10 and e=50

    regards



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