Decision Optimization

 View Only
  • 1.  Transition matrix for State Function

    Posted Sun January 17, 2021 07:34 PM
    The code is assigning jobs with the same group to pre-scheduled time-window. The domain of groups is {1, 2, 3, 4} and there is transitional time when we switch groups.
    tTimes= {<1 1 2> <2 2 2> <3 3 2> <4 4 2>}; //fromGroup toGroup Penalty

    Now, I got the following error in State function, "Exception in presolve: Transition matrix for state function does not satisfy the triangle inequality (path 1->0->1).."
    I could not understand this error since there is no group of "0" in the domain. Can you please tell me what are my mistakes?

    stateFunction MachineGroup with tTimes;
    forall(pt in GroupClock) alwaysEqual(MachineGroup, pt.s, pt.e, pt.g);
    forall(j in Jobs) alwaysEqual(MachineGroup, tasks[j], j.g);


    using CP;
    range Groups = 1..4;
    int nj = ...;
    int GroupTimes[Groups] = ...;
    tuple JobT {
    int j;
    int g;
    int ea;
    int la;
    };
    {JobT} Job=...;
    tuple JobsT {
    int j;
    int g;
    int ea;
    int la;
    };
    {JobsT} Jobs={ <j.j, j.g, j.ea,j.la > | j in Job};

    tuple GroupClockT {
    int g;//Group
    int s;//start
    int e;//end
    };
    {GroupClockT} GroupClock ;
    execute {
    var s=0;var e=0;
    for(var i=1;i<=5;i++)
    for(var p in Groups) {
    e=s+GroupTimes[p];
    GroupClock.add(p, s, e);
    s=e;
    }
    };


    tuple TTimeT {
    key int p1;
    key int p2;
    int t;
    };
    {TTimeT} tTimes;
    execute {
    for(var p1 in Groups) for(var p2 in Groups){
    if(p1!=p2) tTimes.add(p1, p1, 2);
    }
    writeln(tTimes);
    };

    dvar interval tasks[t in Jobs] in t.ea..9999 size 1;
    stateFunction MachineGroup with tTimes;
    cumulFunction BatchSize= sum(t in Jobs) pulse(tasks[t], 1);
    dexpr int totalDelay= sum(j in Jobs) (endOf(tasks[j])-j.ea);

    execute{
    cp.param.TimeMode = "ElapsedTime";
    cp.param.timeLimit=5;
    }
    minimize totalDelay;
    constraints {
    BatchSize <= 4;
    forall(pt in GroupClock) alwaysEqual(MachineGroup, pt.s,pt.e,pt.g);
    forall(j in Jobs) alwaysEqual(MachineGroup, tasks[j], j.g);
    }


    nj=20;
    Job = {
    < 1 4 11 11 >
    < 2 3 12 13 >
    < 3 3 2 2 >
    < 4 1 6 6 >
    < 5 2 9 9 >
    < 6 1 10 10 >
    < 7 3 7 7 >
    < 8 2 2 2 >
    < 9 4 3 3 >
    < 10 2 5 5 >
    < 11 3 5 5 >
    < 12 1 9 9 >
    < 13 1 5 5 >
    < 14 4 10 10 >
    < 15 3 0 0 >
    < 16 4 2 2 >
    < 17 4 1 1 >
    < 18 3 9 9 >
    < 19 2 9 9 >
    < 20 3 5 5 >
    };
    GroupTimes =[2,2,2,2];

    ------------------------------
    Thanks,
    Andy
    ------------------------------

    #DecisionOptimization


  • 2.  RE: Transition matrix for State Function

    Posted Mon January 18, 2021 03:15 AM

    Hi Andy,
    In OPL all transition distance matrices are indexed from 0 to the largest number used in the triples. So here, the matrix is indexed on [0,4]. By default, any value of the matrix that is unspecified is 0, so your matrix looks like:

      0 1 2 3 4
    0 0 0 0 0 0
    1 0 2 0 0 0
    2 0 2 0 0 0
    3 0 2 0 0 0
    4 0 2 0 0 0

    And it does indeed not satisfy the triangle inequality as said by the error: path 1->0->1: d10+d01=0 < d11=2

    You could re-index your values on [0,3] instead of [1,4], but it does not change the problem, your matrix fundamentally does not satisfy the triangle inequality as (on your original indices) for instance : d23+d32=0 < d33=2

    So I think that you should find a slightly different way to model the problem. Here is one idea: if, as you say, you know the set of pre-scheduled time-windows and their state (constraints: alwaysEqual(MachineGroup, pt.s,pt.e,pt.g)). Then maybe you could use one state function per state/group (say MachineGroup[g] for group 'g') that would just constrain the jobs of groups 'g' to be scheduled in the predefined time-windows for state 'g'. These state function would only have one type : '0'. The matrix would just be {<0 0 2>}. And you would post constraints alwaysEqual(MachineGroup[g], pt.s,pt.e,g) for the pt.g==g and also constraints alwaysNoState(MachineGroup[g], ...) in between the predefined time-windows to prevent execution of jobs of group g in between.





    ------------------------------
    Philippe Laborie
    ------------------------------



  • 3.  RE: Transition matrix for State Function

    Posted Mon January 18, 2021 07:10 AM

    Thanks! I have resolved the issue with your feedback. I was confused by the different usage of transition matrix between StateFunction and Sequence. In Sequence, I was able to use any index values of "from" and "to", but In StateFunction, I had to use indexes starting with 0. Anyway, I am good now. 



    ------------------------------
    Andy Ham
    ------------------------------