Decision Optimization

Decision Optimization

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

 View Only

How to evaluate CPLEX CPO random seed variability in OPL ?

  • 1.  How to evaluate CPLEX CPO random seed variability in OPL ?

    Posted Wed October 18, 2017 07:01 AM

    Hi,

     a bit like

    https://www.ibm.com/developerworks/community/forums/html/topic?id=2bbb5d8a-b968-44ff-b4e7-4f9089f4b694&ps=25

    but with CPO

    Let us take a RCPSP example

    .mod

     using CP;
     
     int n=30; // number of random seeds
    int d[1..n]; // duration
    int o[1..n]; // objective
    int iter[1..n]; // iterations

    execute
    {
    cp.param.LogVerbosity="Quiet";
    }

    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]);

    execute {
            cp.param.TimeLimit = 0.1;
    }

    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>]);
    }

    execute {
      for (var t in Tasks) {
        writeln("Task " + t.id + " starts at " + itvs[t].start);
      }
    }

    main {

    //thisOplModel.generate();


    var sum_d=0;
    var sum_o=0;;
    var sum_iter=0;

    writeln("seed objective branches   runtime");

    for(var i=1;i<=thisOplModel.n;i++)
    {

        var opl=new IloOplModel(thisOplModel.modelDefinition);
        var data = thisOplModel.dataElements;
        opl.addDataSource(data);
        
        opl.generate();

        cp.param.randomseed=i;

        
        
        
        var d1=new Date();
        cp.solve();
        var d2=new Date();
        
        thisOplModel.d[i]=d2-d1;
        sum_d+=d2-d1;
        thisOplModel.d[i]=d2-d1;
        thisOplModel.o[i]=Opl.ftoi(Opl.round(cp.getObjValue()));
        sum_o+=thisOplModel.o[i];
        thisOplModel.iter[i]=cp.info.NumberOfBranches;
        sum_iter+=thisOplModel.iter[i];
        writeln(i,"    ",thisOplModel.o[i],"     ",thisOplModel.iter[i],"       ",
        thisOplModel.d[i]/1000);
        cp.clearModel();
    }    

    writeln("-----------------------------------------");
    writeln("average      ",sum_o/thisOplModel.n," ",
    sum_iter/thisOplModel.n," ",sum_d/thisOplModel.n/1000);
    writeln("std dev      ",Opl.standardDeviation(thisOplModel.o),"     ",
    Opl.standardDeviation(thisOplModel.iter),"     ",Opl.standardDeviation(thisOplModel.d)/1000);

    }
     

    .dat

    NbTasks = 122;
    NbRsrcs = 4;

    Capacity = [ 12, 12, 11, 12 ];

    Tasks = {
      < 1, 0, [ 0, 0, 0, 0 ], { 2, 3, 4 } >,
      < 2, 8, [ 0, 10, 0, 0 ], { 40, 48, 61 } >,
      < 3, 5, [ 7, 0, 0, 0 ], { 19, 34, 46 } >,
      < 4, 3, [ 2, 0, 0, 0 ], { 5, 10, 11 } >,
      < 5, 10, [ 0, 0, 8, 0 ], { 6, 13, 32 } >,
      < 6, 9, [ 0, 10, 0, 0 ], { 7, 8, 20 } >,
      < 7, 10, [ 0, 0, 3, 0 ], { 29, 33, 70 } >,
      < 8, 10, [ 1, 0, 0, 0 ], { 9, 12, 16 } >,
      < 9, 5, [ 0, 0, 0, 9 ], { 14, 18, 39 } >,
      < 10, 2, [ 0, 0, 6, 0 ], { 22, 63 } >,
      < 11, 10, [ 4, 0, 0, 0 ], { 48, 58, 117 } >,
      < 12, 2, [ 0, 0, 6, 0 ], { 24, 28, 30 } >,
      < 13, 4, [ 6, 0, 0, 0 ], { 51, 61 } >,
      < 14, 6, [ 6, 0, 0, 0 ], { 15, 61, 110 } >,
      < 15, 7, [ 6, 0, 0, 0 ], { 49, 107 } >,
      < 16, 1, [ 0, 0, 2, 0 ], { 17, 41, 89 } >,
      < 17, 10, [ 0, 0, 0, 5 ], { 40, 64, 80 } >,
      < 18, 9, [ 0, 3, 0, 0 ], { 21, 23, 65 } >,
      < 19, 10, [ 0, 0, 0, 10 ], { 45, 58, 89 } >,
      < 20, 5, [ 7, 0, 0, 0 ], { 29, 37, 43 } >,
      < 21, 1, [ 0, 4, 0, 0 ], { 26, 35, 50 } >,
      < 22, 1, [ 0, 0, 0, 8 ], { 72, 95 } >,
      < 23, 9, [ 1, 0, 0, 0 ], { 57, 63, 73 } >,
      < 24, 10, [ 0, 6, 0, 0 ], { 25, 27, 43 } >,
      < 25, 4, [ 10, 0, 0, 0 ], { 67, 75, 91 } >,
      < 26, 10, [ 0, 0, 8, 0 ], { 36, 71 } >,
      < 27, 6, [ 0, 0, 4, 0 ], { 35 } >,
      < 28, 1, [ 3, 0, 0, 0 ], { 35, 66, 105 } >,
      < 29, 8, [ 0, 0, 0, 6 ], { 108 } >,
      < 30, 5, [ 0, 0, 6, 0 ], { 31, 33, 80 } >,
      < 31, 3, [ 0, 0, 0, 2 ], { 44, 52, 97 } >,
      < 32, 6, [ 10, 0, 0, 0 ], { 47, 67, 82 } >,
      < 33, 2, [ 0, 0, 0, 8 ], { 68, 78, 103 } >,
      < 34, 7, [ 0, 0, 0, 3 ], { 87, 94, 99 } >,
      < 35, 9, [ 0, 0, 3, 0 ], { 47, 56, 90 } >,
      < 36, 5, [ 5, 0, 0, 0 ], { 112 } >,
      < 37, 10, [ 0, 0, 5, 0 ], { 38, 51, 102 } >,
      < 38, 3, [ 7, 0, 0, 0 ], { 119 } >,
      < 39, 2, [ 0, 0, 6, 0 ], { 41, 62, 81 } >,
      < 40, 9, [ 0, 9, 0, 0 ], { 42, 75 } >,
      < 41, 6, [ 0, 1, 0, 0 ], { 57, 66 } >,
      < 42, 3, [ 0, 0, 0, 10 ], { 49, 83, 92 } >,
      < 43, 3, [ 0, 3, 0, 0 ], { 81 } >,
      < 44, 7, [ 8, 0, 0, 0 ], { 49, 74, 92 } >,
      < 45, 1, [ 0, 0, 0, 5 ], { 77 } >,
      < 46, 1, [ 0, 1, 0, 0 ], { 56, 69, 83 } >,
      < 47, 7, [ 10, 0, 0, 0 ], { 104 } >,
      < 48, 5, [ 0, 3, 0, 0 ], { 53, 56, 59 } >,
      < 49, 8, [ 0, 1, 0, 0 ], { 53, 108 } >,
      < 50, 7, [ 0, 0, 7, 0 ], { 53, 54, 60 } >,
      < 51, 1, [ 0, 0, 0, 2 ], { 52, 55, 71 } >,
      < 52, 2, [ 5, 0, 0, 0 ], { 59, 63, 75 } >,
      < 53, 1, [ 0, 0, 0, 3 ], { 102 } >,
      < 54, 4, [ 0, 0, 0, 7 ], { 55, 76, 78 } >,
      < 55, 7, [ 0, 0, 4, 0 ], { 58, 68, 83 } >,
      < 56, 10, [ 0, 0, 2, 0 ], { 62 } >,
      < 57, 9, [ 0, 0, 1, 0 ], { 69, 90 } >,
      < 58, 1, [ 0, 0, 0, 7 ], { 72, 104 } >,
      < 59, 8, [ 0, 0, 1, 0 ], { 62, 70, 113 } >,
      < 60, 1, [ 0, 6, 0, 0 ], { 66, 70, 86 } >,
      < 61, 4, [ 0, 0, 0, 7 ], { 73, 84, 93 } >,
      < 62, 2, [ 0, 0, 0, 1 ], { 72, 87, 88 } >,
      < 63, 8, [ 1, 0, 0, 0 ], { 68, 78 } >,
      < 64, 6, [ 8, 0, 0, 0 ], { 74, 95, 98 } >,
      < 65, 7, [ 0, 9, 0, 0 ], { 77, 88, 105 } >,
      < 66, 2, [ 0, 9, 0, 0 ], { 79, 106 } >,
      < 67, 5, [ 6, 0, 0, 0 ], { 77, 93, 94 } >,
      < 68, 6, [ 0, 0, 0, 6 ], { 84, 85, 99 } >,
      < 69, 4, [ 0, 3, 0, 0 ], { 93, 108 } >,
      < 70, 3, [ 0, 10, 0, 0 ], { 115 } >,
      < 71, 9, [ 0, 0, 0, 1 ], { 79, 86, 114 } >,
      < 72, 4, [ 0, 0, 0, 8 ], { 110 } >,
      < 73, 1, [ 0, 5, 0, 0 ], { 74, 79, 100 } >,
      < 74, 3, [ 1, 0, 0, 0 ], { 82, 85 } >,
      < 75, 9, [ 0, 9, 0, 0 ], { 87, 88, 101 } >,
      < 76, 4, [ 0, 0, 9, 0 ], { 80, 90 } >,
      < 77, 2, [ 7, 0, 0, 0 ], { 85, 98 } >,
      < 78, 8, [ 0, 0, 0, 8 ], { 84, 105 } >,
      < 79, 9, [ 0, 0, 2, 0 ], { 91, 92 } >,
      < 80, 10, [ 0, 0, 0, 7 ], { 81, 91, 103 } >,
      < 81, 8, [ 0, 4, 0, 0 ], { 82 } >,
      < 82, 6, [ 0, 10, 0, 0 ], { 101 } >,
      < 83, 2, [ 0, 0, 3, 0 ], { 94, 95 } >,
      < 84, 5, [ 0, 2, 0, 0 ], { 86, 100 } >,
      < 85, 5, [ 8, 0, 0, 0 ], { 101 } >,
      < 86, 5, [ 8, 0, 0, 0 ], { 89, 107, 111 } >,
      < 87, 2, [ 0, 0, 0, 4 ], { 109 } >,
      < 88, 2, [ 0, 0, 8, 0 ], { 115 } >,
      < 89, 10, [ 0, 0, 0, 7 ], { 109 } >,
      < 90, 6, [ 0, 0, 0, 2 ], { 98, 110, 111 } >,
      < 91, 2, [ 7, 0, 0, 0 ], { 96, 99 } >,
      < 92, 2, [ 0, 0, 0, 6 ], { 96, 103, 116 } >,
      < 93, 8, [ 1, 0, 0, 0 ], { 97, 117 } >,
      < 94, 5, [ 0, 6, 0, 0 ], { 96 } >,
      < 95, 7, [ 5, 0, 0, 0 ], { 97, 119 } >,
      < 96, 10, [ 0, 4, 0, 0 ], { 111, 118 } >,
      < 97, 3, [ 0, 0, 0, 1 ], { 104 } >,
      < 98, 8, [ 0, 6, 0, 0 ], { 100, 102, 107 } >,
      < 99, 1, [ 0, 0, 0, 4 ], { 121 } >,
      < 100, 9, [ 0, 6, 0, 0 ], { 106 } >,
      < 101, 7, [ 0, 0, 0, 10 ], { 118 } >,
      < 102, 1, [ 0, 5, 0, 0 ], { 113 } >,
      < 103, 10, [ 0, 0, 0, 2 ], { 112 } >,
      < 104, 1, [ 0, 0, 0, 4 ], { 106 } >,
      < 105, 1, [ 0, 0, 0, 4 ], { 113 } >,
      < 106, 2, [ 0, 0, 0, 6 ], { 114 } >,
      < 107, 9, [ 0, 0, 0, 2 ], { 109 } >,
      < 108, 2, [ 0, 2, 0, 0 ], { 121 } >,
      < 109, 7, [ 0, 4, 0, 0 ], { 118 } >,
      < 110, 4, [ 0, 0, 6, 0 ], { 112, 116 } >,
      < 111, 6, [ 0, 0, 7, 0 ], { 117, 119 } >,
      < 112, 1, [ 0, 8, 0, 0 ], { 120 } >,
      < 113, 6, [ 0, 0, 0, 10 ], { 114 } >,
      < 114, 5, [ 0, 6, 0, 0 ], { 115 } >,
      < 115, 6, [ 9, 0, 0, 0 ], { 116 } >,
      < 116, 1, [ 0, 0, 0, 7 ], { 120 } >,
      < 117, 9, [ 0, 0, 0, 8 ], { 120 } >,
      < 118, 7, [ 0, 0, 0, 9 ], { 121 } >,
      < 119, 5, [ 0, 0, 10, 0 ], { 122 } >,
      < 120, 4, [ 0, 0, 0, 6 ], { 122 } >,
      < 121, 10, [ 0, 0, 8, 0 ], { 122 } >,
      < 122, 0, [ 0, 0, 0, 0 ], {  } >
     };

    gives

    seed objective branches   runtime
    1    146     42438       0.111
    2    146     42957       0.107
    3    146     44281       0.106
    4    146     43253       0.107
    5    144     46651       0.108
    6    145     50591       0.109
    7    145     49176       0.106
    8    145     49815       0.106
    9    144     49871       0.108
    10    144     50600       0.107
    11    144     50491       0.107
    12    145     51246       0.108
    13    144     47336       0.107
    14    143     47893       0.11
    15    144     44036       0.107
    16    144     49669       0.108
    17    146     43558       0.107
    18    145     48943       0.106
    19    145     49549       0.107
    20    141     47410       0.108
    21    145     47841       0.108
    22    143     51447       0.107
    23    144     51109       0.107
    24    146     46076       0.107
    25    145     51643       0.106
    26    145     44914       0.107
    27    144     44453       0.109
    28    145     53116       0.106
    29    144     51382       0.107
    30    145     47474       0.111
    -----------------------------------------
    average      144.6 47973.966666667 0.1075
    std dev      1.083205121     3020.943698949     0.001335415

    regards

    PS:

    Evaluating CPO random seed variability will increase confidence.


    #DecisionOptimization
    #OPLusingCPOptimizer