Originally posted by: hacimehmet

I have modelled an assembly line balancing problem which is a kind of bin packing problem by using constraint programming. I attached the mod file in this post.

stationnumber[nbtask] is a decision variable which denotes the station number assigned to the task. Furthermore, stationtime[nbstation] denotes the station time as a decision variable. When any task is assigned to a station, the task time is added on the station time. A total station time consists of the whole assigned task times.

I would like to improve a variable and value selection mechanism for this problem. The task which has the maximum task time should be selected as a variable, and then the station number which has the minimum station time should be assigned as variable value.

To explain my algorithm with an example; The following figure illustrates the precedence relation between tasks, and the task number and task time are given in the following table. The station number is given as three (i.e. the domain interval of stationnumber[] is one to three). The initial value of stationtime[] is set as {0,0,0}.

Task number	1	2	3	4	5	6	7
Task time	1	5	4	3	4	6	5

 

Iteration 1: Assinged tasks={ }  Unassigned tasks={1,2,3,4,5,6,7}

The task which has the maximum task time among the unassigned tasks is task 6. The task 6 is selected and assigned to the station 3 randomly. stationtime[] array is updated as ={0,0,6}.

Iteration 2: Assinged tasks={6}  Unassigned tasks={1,2,3,4,5,7}

The tasks which have the maximum task time among the unassigned tasks are task 2 and 7. The task 2 is selected randomly. The stations which have the minimum station time according to the previous iterations are station 1 and 2. The task 2 is assigned the station 1 randomly. stationtime[] array is updated as ={5,0,6}.

Iteration 3: Assinged tasks={2,6}  Unassigned tasks={1,3,4,5,7}

The task which has the maximum task time among the unassigned tasks is task 7. The task 7 is assigned to station 3 by considering precedence relations. stationtime[] array is updated as ={5,0,11}.

Iteration 4: Assinged tasks={2,6,7}  Unassigned tasks={1,3,4,5}

The tasks which have the maximum task time among the unassigned tasks are task 3 and 5. The task 5 is selected randomly. The station which has the minimum station time according to the iteration 3 is station 2. The task 5 is assigned the station 2. stationtime[] array is updated as ={5,4,11}.

Iteration 5: Assinged tasks={2,5,6,7}  Unassigned tasks={1,3,4}

The task which has the maximum task time among the unassigned tasks is task 3. The station which has the minimum station time is station 2. The task 3 is assigned the station 2. stationtime[] array is updated as ={5,8,11}.

Iteration 6: Assinged tasks={2,3,5,6,7}  Unassigned tasks={1,4}

The task which has the maximum task time among the unassigned tasks is task 4. The station which has the minimum station time is station 1. The task 4 is assigned the station 1. stationtime[] array is updated as ={8,8,11}.

Iteration 7: Assinged tasks={2,3,4,5,6,7}  Unassigned tasks={1}

The task 1 is the last unassigned task. The stations which have the minimum station time are station 1 and 2. The task 1 is assigned the station 1 subject to the precedence relations. stationtime[] array is updated as ={9,8,11}.

There is no unassigned task, therefore the algorithm is terminated. The maximum station time is reported as 11 and, the task assignment combination is also reported as station1={1,2,4}, station2={3,5} and station3={6,7}.

 

 

Consequently, i want to learn how can i use "stationtime" decision variable in value selection process. 

I attached the Java code that uses random selection as value selection rule.

 

 

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: ChrisBr

Hello,

Sorry for the delay.

One way to use the current domain of a decision variable in value selection process for another variable is to write a dedicated int-value-chooser.

  static public class ChooseSmallestStationTime extends IloCustomIntValueChooser {
    IloIntVar[][] _stationtime;
    int _nbmodels;
    int _nbstations;
    
    public ChooseSmallestStationTime(IloCP cp, IloIntVar[][] stationtime) throws IloException {
      super(cp);
      _stationtime = stationtime;
      _nbmodels = _stationtime.length;
      _nbstations = _stationtime[0].length;
    }
    // actually vars=stationnumber
    // i=min(selectingrule) for vars[i] not fixed yet
    public int choose(IloCP cp, IloIntVar[] vars, int i) {
      int best = IloCP.IntMax;
      IloIntVar var = vars[i];
      int selId = (int)cp.getMin(var);
      java.util.Iterator it = cp.iterator(var); 
      while (it.hasNext()) {
        int currId = ((Integer)(it.next())).intValue();
        if ((currId>=0) && (currId<_nbstations)) {
          // don't know how you manage the different models
          // here we use the sum of stationtime for all models
          int curr = 0;
          for (int m = 0; m < _nbmodels; m++)
            curr += (int)cp.getMin(_stationtime[m][currId]);
          if (curr < best) {
            best = curr;
            selId = currId;
          }
        }
      }
      return selId;
    }
  }

Then:

IloVarSelector varSel = cp.selectLargest(cp.explicitVarEval(stationnumber, selectingrule));
IloIntValueChooser valChooser = new Karma_modelli_MHDP.ChooseSmallestStationTime(cp, stationtime);
IloSearchPhase phase = cp.searchPhase(stationnumber, cp.intVarChooser(varSel), valChooser);
cp.setSearchPhases(phase); 

Please note that this could lead to increase of the solving time.

I hope this helps,

Chris.

 

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: hacimehmet

Hello,

Firstly, I am sorry for lateness

Thank you very much Chris. This is exactly what I need.

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: hacimehmet

Thanks again your helps Chris. This value selection strategy didnot produce good solution. And so, I want to try some different strategies.

I would like to improve a new value selection strategy with different rules based on variable rankings. For example:

1. rule: If variable rate is smaller than 0.2, then the variable take value which have biggest station times.

2. rule: If variable rate is between 0.2 and 0.8, then the variable take random value.

3. rule: If variable rate is bigger than 0.8, then the variable take value which have smallest station times.

 

I could encode the rule 1 and 3 but I could not write the code for rule 2. The code block which is given below give an error, because the values that remove from domain of variables after propagation can be assigned the variable. How can I correct this?

Or is there any different way to encode these rules?

 

       static public classChooseSmallestStationTime extendsIloCustomIntValueChooser {

       IloIntVar[][] _stationtime;

                 int _nbmodels;

                 int _nbstations;

                 int _earliest[]={1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 8};

                 int _latest[]= { 1, 7, 8, 8, 8, 8, 8, 5, 6, 6, 7, 7, 7, 8, 8, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 7, 8, 8};

                 float rate[]= { 0.08, 0.29, 0.57, 1.00, 0.33, 0.27, 0.27, 0.85, 0.79, 0.60, 0.78, 0.19, 0.78, 0.79, 0.71, 0.71, 0.21, 0.29, 0.61, 0.98, 0.49, 0.52, 0.44, 0.15, 0.35, 0.96, 0.73, 0.79};

               publicChooseSmallestStationTime(IloCP cp, IloIntVar[][] stationtime) throwsIloException {

                   super(cp);

                   _stationtime= stationtime;

                   _nbmodels= _stationtime.length;

                   _nbstations= _stationtime[0].length;

                 }

                   // actually vars=stationnumber

                 // i=min(selectingrule) for vars[i] not fixed yet

                 public intchoose(IloCP cp, IloIntVar[] vars, int i) {

                   int best= IloCP.IntMax;

                   IloIntVar var= vars[i];

                   int selId= (int)(cp.getMax(var));

                java.util.Iterator it= cp.iterator(var);

                   if(rate[i]>=0.80){

                   while(it.hasNext()) {

                     int currId= ((Integer)(it.next())).intValue();

                     if((currId>=_earliest[i]) && (currId<_latest[i])) {

                       // don't know how you manage the different models

                       // here we use the sum of stationtime for all models

                       int curr= 0;

                       for(int m= 0; m< _nbmodels; m++)

                         curr+= (int)cp.getMin(_stationtime[m][currId]);

                       if(curr< best) {

                         best= curr;

                         selId= currId;

               }

            }

           }

         }

 

                if(rate[i]>0.20 &&rate[i]<0.80 ){

                  

                     cp.getDomainSize(var);

                double STR=_earliest[i]+((_latest[i]-_earliest[i])*Math.random());

                     int rndnum= (int) (STR);

                       selId= rndnum;

                 } 

                

                   if(rate[i]<=0.20){

                          while(it.hasNext()) {

                            int currId= ((Integer)(it.next())).intValue();

                            if((currId>=_earliest[i]) && (currId<_latest[i])) {

                              // don't know how you manage the different models

                              // here we use the sum of stationtime for all models

                              int curr= 0;

                              for(int m= 0; m< _nbmodels; m++)

                                curr+= (int)cp.getMax(_stationtime[m][currId]);

                              if(curr< best) {

                                best= curr;

                                selId= currId;

                              }

                            }

                          }

                          }

                                     return selId;

                 }

        }

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: GGR

Hi

 

Your selector does not assume that the tuple(variable, value) is valid. That is at the time you the you compute the chosen value of the selected variable, it happens that this value is no more a possible assignment of the variable. That is why your search may not work.

 

To be sure of having a valid value you have to check it first. That is verify that the value is in the domain of the variable. To achieve that, please have a look to the member isInDomain of the solver of the actual selection. More precisely, have a look to the member function of IloCP class isInDoamin.

 

Hope taht help

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: hacimehmet

 

 I'm sorry, I forget to thanks to you.

Thanks for your help. it works.

#ConstraintProgramming-General
#DecisionOptimization

Originally posted by: hacimehmet

Hi, I have one more question about variable selection. I want to change an array that I use for variable selection while programme is running.  How can I update this array? For this, I wrote the following code block. So, I plan to update the array in the time. But, it gave the following error.  How can I correct this error?

ilog.concert.IloException: IloInt IloIntVarChooser::choose(...) : unfixed variables remains while the function return -1

Note: I know this code is the same as IloVarSelector varSel = cp.selectLargest(cp.explicitVarEval(stationnumber, selectingrule)); but my main problem is about updating the selectingrule array while the programme is running.

 

        static public classChoosemaximum extendsIloCustomIntVarChooser {

               publicChoosemaximum(IloCP cp) throwsIloException {

                   super(cp);

               };

              

              

             

               double[] selectingrule= {270, 270, 100, 140, 190, 290, 335, 179, 485, 199, 248, 248, 248, 248, 248, 260, 260, 260, 286, 241, 260, 60, 260, 230, 230, 171, 480, 174, 170, 300, 105, 248, 180, 235, 330, 276, 248, 440, 260, 270, 160, 110, 270, 430, 243, 190, 160, 110, 386, 0, 200, 242, 186, 270, 150, 73, 466, 230, 134, 181, 107, 271, 133, 266, 119, 181, 139, 149, 189, 149, 149, 277, 192, 333, 229, 130, 608, 0, 0, 117, 117, 342, 138, 240, 240, 87, 0, 294, 198, 147, 267, 151, 190, 78, 135, 235, 425, 90, 107, 0, 423, 128, 287, 105, 158, 439, 159, 246, 188, 184, 680, 70, 185, 185, 0, 881, 166, 153, 185, 128, 387, 301, 51, 227, 138, 181, 731, 848, 227, 121, 317, 121, 439, 125, 129, 143, 138, 107, 312, 241, 228, 186, 249, 371, 90, 136, 90, 90, 66, 90, 102, 146, 101, 371, 118, 285, 201, 148, 148, 79, 148, 91, 52, 215, 336, 869, 125, 68, 121, 80, 207, 178, 132, 121, 150, 81, 30, 63, 351, 274, 82, 75, 145, 120, 495, 99, 169, 65, 500, 92, 42, 263, 213, 187, 164, 86, 107, 108, 117, 78, 0, 472, 72, 30, 112, 216, 0, 220, 183, 183, 220, 74, 139, 339, 202, 102, 550, 406, 147, 0, 0, 5, 128, 68, 100, 68, 310, 835, 740, 213, 68, 390, 130, 304, 85, 403, 21, 236, 129, 1019, 34, 115, 68, 910, 102, 578, 101, 1300, 0, 178, 0, 190, 100, 352, 92, 28, 83, 242, 141, 303, 217, 58, 199, 196, 91, 44, 99, 50, 421, 129, 114, 196, 215, 378, 0, 270, 345, 193, 140, 100, 150, 412, 0, 170, 252, 198, 301, 301, 121, 52, 326, 84, 1386, 527, 968, 1000, 538};

                   

              

               public intchoose(IloCP cp, IloIntVar [] vars) {

                    double best= Double.MIN_VALUE;

                   int bestIndex=-1;

                   int n= vars.length;

 

                  for(int i= 0; i< n; i++) {

                       if(!cp.isFixed(vars[i])){

                      while(selectingrule[i] > best) {

                               best= selectingrule[i];

                               bestIndex= i;

                               }

                       }           

                       }

              System.out.println("aaaa "+" ="+ bestIndex);

                  

              return bestIndex;

               }

 

           }

#ConstraintProgramming-General
#DecisionOptimization