Decision Optimization

 View Only
  • 1.  multiple transition-matrix on the same sequence

    Posted Tue February 23, 2021 11:23 AM
    Edited by System Fri January 20, 2023 04:31 PM
    Suppose each job is characterized by group and location. Now, we need to prohibit transitions between groups and penalize transitions between locations. How can I consider two different transitional matrices in the same sequence?
    I created a dummy sequence to consider the second transition matrix. It works, but not efficient for a large-scale instance (50 machines; 10000 jobs). Is there other way? Thanks!

    using CP;

    tuple t_Job {
    key int j;
    int sz;
    int grp;
    int loc;
    } {t_Job} Jobs = {
    <1, 1, 100, 80>,
    <2, 2, 100, 40>,
    <3, 3, 100, 80>,
    <4, 4, 200, 40>,
    <5, 5, 200, 40>,
    <6, 6, 200, 80>,
    <7, 7, 200, 40>,
    <8, 8, 300, 80>,
    <9, 9, 300, 40>,
    <10,10,300, 80>};

    tuple t_forbid_g2g {
    key int g1;
    key int g2;
    int d;
    } {t_forbid_g2g} forbid_g2g = {
    <100, 200, 99999>,
    <100, 300, 99999>};


    tuple t_penalty_l2l {
    key int l1;
    key int l2;
    int d;
    } {t_penalty_l2l} penalty_l2l = {
    <80, 40, 30>,
    <40, 80, 30>};


    dvar interval itvj[j in Jobs] size j.sz;

    dvar sequence seqMch
    in all(j in Jobs) itvj[j]
    types all(j in Jobs) j.loc;
    //types all(j in Jobs) j.grp;
    minimize max(j in Jobs)endOf(itvj[j]);
    subject to {
    noOverlap(seqMch,forbid_g2g,true);
    //noOverlap(seqMch,penalty_l2l,true);
    }

    /*
    //create dummy sequence to consider the second transition matrix
    using CP;

    tuple t_Job {
    key int j;
    int sz;
    int grp;
    int loc;
    } {t_Job} Jobs = {
    <1, 1, 100, 80>,
    <2, 2, 100, 40>,
    <3, 3, 100, 80>,
    <4, 4, 200, 40>,
    <5, 5, 200, 40>,
    <6, 6, 200, 80>,
    <7, 7, 200, 40>,
    <8, 8, 300, 80>,
    <9, 9, 300, 40>,
    <10,10,300, 80>};

    tuple t_forbid_g2g {
    key int g1;
    key int g2;
    int d;
    } {t_forbid_g2g} forbid_g2g = {
    <100, 200, 99999>,
    <100, 300, 99999>};


    tuple t_penalty_l2l {
    key int l1;
    key int l2;
    int d;
    } {t_penalty_l2l} penalty_l2l = {
    <80, 40, 30>,
    <40, 80, 30>};


    dvar interval itvj[j in Jobs] size j.sz;

    dvar sequence Mch
    in all(j in Jobs) itvj[j]
    types all(j in Jobs) j.loc;

    dvar sequence MchDummy
    in all(j in Jobs) itvj[j]
    types all(j in Jobs) j.grp;

    minimize max(j in Jobs)endOf(itvj[j]);
    subject to {
    noOverlap(Mch, penalty_l2l,true);
    noOverlap(MchDummy,forbid_g2g ,true);
    }
    */

    ------------------------------
    Andy Ham
    ------------------------------
    #DecisionOptimization


  • 2.  RE: multiple transition-matrix on the same sequence

    Posted Tue February 23, 2021 01:58 PM
    Hi,
    have you tried typeOfNext ?
    regards

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



  • 3.  RE: multiple transition-matrix on the same sequence

    Posted Tue February 23, 2021 05:00 PM
    I believe we can tag an interval with one "type" on the sequence. So, "typeOfNext" does not provide me a solution since I need to tag an interval with two different "types".
    However, I am using "typeOfNext" in behalf of "transition matrix" since the former delivers a faster performance for my large scale instances.


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



  • 4.  RE: multiple transition-matrix on the same sequence

    Posted Wed February 24, 2021 02:40 AM
    Hi,

    so on top of typeOfNext vs noOverlap, you could use several sequences with the same intervals.

    regards

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



  • 5.  RE: multiple transition-matrix on the same sequence

    Posted Wed February 24, 2021 06:57 AM

    I did create a dummy sequence to consider the second transition matrix. Please see the following code. It works well, but not efficient for a large scale instance (50 machines; 2000 jobs).  The particular test instance has a huge number of forbidden transitions. Better way to model, please? Thanks!


    dvar sequence Mch in all(j in Jobs) itvj[j] types all(j in Jobs) j.loc;
    dvar sequence MchDummy in all(j in Jobs) itvj[j] types all(j in Jobs) j.grp;

    noOverlap(Mch, penalty_l2l,true);
    noOverlap(MchDummy,forbid_g2g ,true);



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



  • 6.  RE: multiple transition-matrix on the same sequence

    Posted Mon March 01, 2021 03:53 AM


    I think there are two way to model your problem:

    1- Either by using two sequences with the same interval variables and the two transition matrices (as you did). Note that you could additionally tell the engine that the two sequences are the same by adding a 'sameSequence' constraint. This can potentially speed-up the search because internally some structures will be shared by the two sequences).

    2- Or use a unique sequence with a unique transition matrix that is indexed on the different relevant pairs (group/position). This will be the best formulation in case you do not have too many different pairs (group/position). On your small example you would have 6 types (and probably less as you can compact the matrix on the indexes that have the same transition time (like here: 80<->40: these two types are equivalent given the data)

    Types of the unique matrix: 0…5

    0 -> (100,80)
    1 -> (100,40)
    2 -> (200,40)
    3 -> (200,80)
    4 -> (300,40)
    5 -> (300,80)
    

    Transitions:

    0->1: 30
    0->2: 99999
    0->3: 99999
    0->4: 99999
    0->5: 99999
    1->0: 30
    1->2: 99999
    1->3: 99999
    1->4: 99999
    1->5: 99999
    …


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



  • 7.  RE: multiple transition-matrix on the same sequence

    Posted Mon March 01, 2021 04:32 PM
    Thanks! Actually, I am using the second method that has been best performing so far. I cannot apply the sameSequence since the two sequence variables contain a different set of intervals in my real problem: sequence_1 contains (interval set A) and sequence_2 contains (interval set A and interval set B). Thanks for helping me look into the problem from different perspectives.

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



  • 8.  RE: multiple transition-matrix on the same sequence

    Posted Tue March 02, 2021 03:02 AM
    Not sure that will be useful but if two sequences use the same subset of intervals, you can also have a look at constraints "sameCommonSubsequence", which says that the sequences are the same on the intervals they have in common (the A in your case). This being said, in the case of this constraint, I do not think it would improve the speed. So my comment is more to let you know about this constraint in case you have a real use-case for it in the future ... In general, it is used when you have a mapping between the two sets of interval variables.

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