Originally posted by: Viktoria_Austria

Hi there,

 

I have a question concerning the OPL implementation of the staticLex method. Actually, I have already implemented a MOO problem using OPL in the CP Optimizer environment. However, for comparison reasons, I would also need MIP results. I have seen that it is possible now to use the staticLex function also for my MIP model. But I am afraid I have some troubles with this "new" function.

 

My CP staticLex, including necessary definitions, looks as follows:

dexpr int Obj_SumPrios = sum (i in ProjectPRIONodes) (Prios[i] * presenceOf(w[i]));
dexpr int Obj_Makespan = endOf(w[MultiProjectFinishNode]);
dvar int z1;
dvar int z2;

minimize staticLex(z1 * Obj_Makespan + z2 * Obj_SumPrios,(1-z1) * Obj_Makespan + (1-z2) * Obj_SumPrios);

 

I have done the following for the MIP model:

 

 dvar    boolean x[AllActivities];                            //DV: node i is selected to be performed = 1; 0 otherwise
 dvar    boolean y[AllActivities][AllTimeslots];                //DV: node i is selected and completed at the end of time slot t = 1; 0 otherwise

 dvar boolean z1;
 dvar boolean z2;

dexpr int Obj_SumPrios = (sum (i in ProjectPRIONodes ) (Prios[i] * x[i])) ;  
dexpr int Obj_Makespan = (sum ( t in AllTimeslots ) t * y[MultiProjectFinishNode][t]) ;

 

--> the z1 and z2 are necessary since I have implemented a MOO solution method (balanced box method, see Boland et al. 2015) where it is necessary to switch within parts of the solution space (boxes). As far as I have seen, it is not possible to copy the staticLex function as I used it here for the CP Optimizer.. Do you know what/how I would have to change?

 

Thank very much in advance for your response!

 

Best,

Viktoria

 

 

#CPLEXOptimizers
#DecisionOptimization

Hi,

at https://www.ibm.com/developerworks/community/forums/html/topic?id=abac189a-0b99-4a08-bedf-78bbf919e14d

you have a very easy staticLex example for MIP

In your case you have a multiply between a binary decision variable and an integer decision variable so you could have a look at

How to multiply a decision variable by a boolean decision variable in CPLEX ?

in

https://www.linkedin.com/pulse/how-opl-alex-fleischer/

regards

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Viktoria_Austria

Hi Alex,

 

Thank you very much! I would have another question..

 

if the two decision variables z1 and z2 are no boolean but integer decision variables, I have the problem that my linearization does not work out and I am not sure if there is another way doing this in cplex?:

dvar int z1;
 dvar int z2;

dexpr int Obj_Makespan = (sum ( t in AllTimeslots ) t * y[MultiProjectFinishNode][t]) ;
dexpr int Obj_SumPrios = (sum (i in ProjectPRIONodes ) (Prios[i] * x[i])) ;  

dvar int OSP1;
dvar int OMS1;

dvar int OSP2;
dvar int OMS2;

staticLex(OMS1+OSP1,OMS2+OSP2);

z1 + Obj_Makespan <= 1 + OMS1;
    z2 + Obj_SumPrios <= 1 + OSP1;
    
    (1-z1) + Obj_Makespan <= 1 + OMS2;  
    (1-z2) + Obj_SumPrios <= 1 + OSP2;

 

Best

Viktoria

 

 

PS: In case that the full code is necessary:

 

 

   
 int    A = ...;                                             //Amount of activity nodes i (incl. start and destination node)
 int    R = ...;                                              //Amount of resources r. One resource can be utilized by multiple activities
 int    T = ...;                                            //Amount of timeslots t
 
 range    AllActivities = 0..(A-1);                            //all activities (performing start depot, performing production nodes, performing destination depot)
 range    AllResources = 1..R;                                //all resources
 range    AllTimeslots = 1..T;                                //all timeslots
    
 {int}     ProjectPRIONodes = ...;
 int    Prios[ProjectPRIONodes] = ...;
 
 string ResourceNames[AllResources] = ...;                    
 float     C[AllResources] = ...;                                
 int     Dmin[AllActivities] = ...;                        
 int    DT[AllActivities] = ...;                            
 float    p[AllActivities] = ...;                                
 float    Q[AllActivities][AllResources] = ...;            
          

 tuple Adjacency                                            
     {
     int src;                                                
     int trg;                                                
     }
 {Adjacency} adjacencies = ...;                                
 {int} Pre[trg in AllActivities] = { src | <src,trg> in adjacencies };         
 {int} Suc[src in AllActivities] = { trg | <src,trg> in adjacencies };         
 
int     MultiProjectFinishNode = ...;            
{int}     ProjectEndNodes = ...;                                    
 
 dvar    boolean x[AllActivities];                            //DV: node i is selected to be performed = 1; 0 otherwise
 dvar    boolean y[AllActivities][AllTimeslots];                //DV: node i is selected and completed at the end of time slot t = 1; 0 otherwise

 dvar    boolean s[AllActivities][AllTimeslots];                //DV: node i is selected and started the first time at timeslot t = 1; 0 otherwise
 dvar    boolean w[AllActivities][AllTimeslots];                //DV: node i is selected and started at timeslot t = 1; 0 otherwise

 dvar int z1;
 dvar int z2;

 dexpr int Obj_Makespan = (sum ( t in AllTimeslots ) t * y[MultiProjectFinishNode][t]) ;
 dexpr int Obj_SumPrios = (sum (i in ProjectPRIONodes ) (Prios[i] * x[i])) ;  

 

//CP Optimizer objective: minimize staticLex(z1 * Obj_Makespan + z2 * Obj_SumPrios,(1-z1) * Obj_Makespan + (1-z2) * Obj_SumPrios);

 

//MIP constraints:

 subject to {

            
            
        FirstStart: s[0][1] == 1;

    //    LastEnd: x[MultiProjectFinishNode] == 1;

        forall (i in AllActivities)
          EndNotOrOnce: sum ( t in AllTimeslots ) y[i][t] == x[i];
    
        forall (i in AllActivities)
          StartNotOrOnce: sum ( t in AllTimeslots ) s[i][t] == x[i];  

        forall (a in adjacencies : p[a.src] == 0 )
            sum (j in Suc[a.src]) x[j] == x[a.src] ;    
            
        forall (a in adjacencies : p[a.src] == 1 )
            x[a.trg] >=  x[a.src] ;
          
        forall (a in adjacencies : p[a.trg] == 2)
            sum (j in Pre[a.trg]) x[j] == x[a.trg] ;  
          

        forall ( a in adjacencies, t in AllTimeslots : p[a.src] == 0 && p[a.trg] <= 1  )
            sum (j in Suc[a.src]) s[j][t] == y[a.src][t];
                    
        forall ( a in adjacencies, t in AllTimeslots : p[a.src] == 1 && p[a.trg] <= 1 )
            y[a.src][t] == s[a.trg][t];

        forall ( a in adjacencies, t in AllTimeslots : p[a.trg] == 2 )
             sum (j in Pre[a.trg]) y[j][t] == s[a.trg][t];
     
 
        forall ( i in ProjectEndNodes )
            EndBeforeStartFinal: sum(t in AllTimeslots) t * y[i][t] <= sum(t in AllTimeslots) t * s[MultiProjectFinishNode][t];
 
        forall (r in AllResources, t in AllTimeslots)
            AdhereToCapacity: (sum (i in AllActivities) w[i][t] * Q[i][r]) <= C[r];

        forall ( i in AllActivities, t in AllTimeslots )
              DetermineDuration: sum (o in 1..t ) (s[i][o] - y[i][o]) == w[i][t];
       
       
          forall ( i in AllActivities ){
                LimitDurationMin: Dmin[i] * x[i] <= sum (o in AllTimeslots) ( w[i][o] );

     }                    
     
    ctMS_lower:
        Obj_Makespan >= 0;
        
    ctMS_upper:
        Obj_Makespan <= infinity;
        
    ctPrios_lower:
        Obj_SumPrios >= 0;
    
    ctPrios_upper:
        Obj_SumPrios <= infinity;        
                  
    

}

 

//Balanced Box Method:

main {

  thisOplModel.generate();
 
    writeln("cplex.solve()");
  thisOplModel.z1.LB = thisOplModel.z1.UB = 1; //statt 100000
  thisOplModel.z2.LB = thisOplModel.z2.UB = 0;
  cplex.solve();
 
  var minMS = thisOplModel.Obj_Makespan.solutionValue;
  var maxPrio = thisOplModel.Obj_SumPrios.solutionValue;
 
  thisOplModel.z1.LB = thisOplModel.z1.UB = 0;
  thisOplModel.z2.LB = thisOplModel.z2.UB = 1; //statt 100000
  cplex.solve();
 
  var maxMS = thisOplModel.Obj_Makespan.solutionValue;
  var minPrio = thisOplModel.Obj_SumPrios.solutionValue;
 
  writeln("Absolute Bounds: (", minMS, ", ", maxPrio, "), (", maxMS, ", ", minPrio ,")");

  var L = new Array();
  var LIdx = 0;
  L[LIdx] = new Object();
  L[LIdx].MS = minMS;
  L[LIdx].Prio = maxPrio;
  LIdx = LIdx + 1;
  L[LIdx] = new Object();
  L[LIdx].MS = maxMS;
  L[LIdx].Prio = minPrio;
  LIdx = LIdx + 1;
 
  var PQ = new Array();
  var rect = new Object();
  rect.Z1 = new Object();
  rect.Z1.MS = minMS;
  rect.Z1.Prio = maxPrio;
  rect.Z2 = new Object();
  rect.Z2.MS = maxMS;
  rect.Z2.Prio = minPrio;
  PQ[0] = rect;
 
  var curr = Infinity;  
  //writeln("OF1 makespan; OF2 priorities");
  //writeln("PQ length ", PQ.length, " UB Prios: ", thisOplModel.ctPrios_upper.UB);    
  while ( PQ.length > 0 ) {
    rect = PQ[0];
    PQ.reverse();
    PQ.length = PQ.length - 1;
    PQ.reverse();
    
    //writeln("Search MS first within: [ (", rect.Z1.MS, ", ", rect.Z1.Prio, "), (", rect.Z2.MS, ", ", rect.Z2.Prio, ") ] ");
    var prioHalf = Math.floor((rect.Z1.Prio + rect.Z2.Prio) / 2.0);
    
    if (prioHalf > rect.Z2.Prio)
    {
    // RB -> unteres Rechteck
    thisOplModel.ctPrios_upper.UB = prioHalf;
    thisOplModel.ctPrios_lower.LB = rect.Z2.Prio;
    thisOplModel.ctMS_upper.UB = rect.Z2.MS;
    thisOplModel.ctMS_lower.LB = rect.Z1.MS;
    
    
    //writeln("cp.solve()");
    thisOplModel.z1.LB = thisOplModel.z1.UB = 1; //maxPrio + 1;
    thisOplModel.z2.LB = thisOplModel.z2.UB = 0;
    
    writeln("Search MS 1st within RB: [ (", rect.Z1.MS, ", ", prioHalf, "), (", rect.Z2.MS, ", ", rect.Z2.Prio, ") ]s ");
    
    if ( cplex.solve() )
    {    
      writeln("solved f1, f2: ");    
      if (thisOplModel.Obj_Makespan != rect.Z2.MS && thisOplModel.Obj_SumPrios != rect.Z2.Prio) {
          L[LIdx] = new Object();                            
          L[LIdx].MS = thisOplModel.Obj_Makespan.solutionValue;            
          L[LIdx].Prio = thisOplModel.Obj_SumPrios.solutionValue;        
          LIdx = LIdx + 1;                                
          //RB2:                                            
        var rb2 = new Object();
        rb2.Z1 = new Object();
          rb2.Z1.MS = thisOplModel.Obj_Makespan.solutionValue;
        rb2.Z1.Prio = thisOplModel.Obj_SumPrios.solutionValue;
        rb2.Z2 = rect.Z2;
          
        PQ[PQ.length] = rb2;
        writeln("  Gefunden: ", thisOplModel.Obj_Makespan, " ", thisOplModel.Obj_SumPrios);
        writeln("  Neues Rechteck: [ (", rb2.Z1.MS, ", ", rb2.Z1.Prio, "), (", rb2.Z2.MS, ", ", rb2.Z2.Prio, ") ] ");     
       }
    }    
    // R^T -> oberes Rechteck:
    thisOplModel.ctPrios_upper.UB = rect.Z1.Prio;
    thisOplModel.ctPrios_lower.LB = prioHalf;
    thisOplModel.ctMS_upper.UB = thisOplModel.Obj_Makespan - 1;
    thisOplModel.ctMS_lower.LB = rect.Z1.MS;
    
    writeln("cplex.solve()");
    thisOplModel.z1.LB = thisOplModel.z1.UB = 0;
    thisOplModel.z2.LB = thisOplModel.z2.UB = 1;

    writeln("Search Prio 1st RT: [ (", rect.Z1.MS, ", ", rect.Z1.Prio, "), (", thisOplModel.Obj_Makespan - 1, ", ", prioHalf, ") ] ");
      
    if ( cplex.solve() )
    {    
      writeln("solved f2, f1: ");
      if (thisOplModel.Obj_Makespan != rect.Z1.MS && thisOplModel.Obj_SumPrios != rect.Z1.Prio) {
          L[LIdx] = new Object();
          L[LIdx].MS = thisOplModel.Obj_Makespan.solutionValue;
          L[LIdx].Prio = thisOplModel.Obj_SumPrios.solutionValue;
          LIdx = LIdx + 1;
          var rb3 = new Object();
          rb3.Z2 = new Object();
          rb3.Z2.MS = thisOplModel.Obj_Makespan.solutionValue;
          rb3.Z2.Prio = thisOplModel.Obj_SumPrios.solutionValue;
          rb3.Z1 = rect.Z1;
          PQ[PQ.length] = rb3;
        //writeln("  UB Prios: ", thisOplModel.ctPrios_upper.UB, " LB Prios: ", thisOplModel.ctPrios_lower.LB, " UB MS: ", thisOplModel.ctMS_upper.UB, " LB MS: ", thisOplModel.ctMS_lower.LB);    
          writeln("  Gefunden: ", thisOplModel.Obj_SumPrios, " ", thisOplModel.Obj_Makespan );     
        writeln("  Neues Rechteck: [ (", rb3.Z1.MS, ", ", rb3.Z1.Prio, "), (", rb3.Z2.MS, ", ", rb3.Z2.Prio, ") ] ");
      }
    }
    }           
  }
       
  for ( var l = 0; l < L.length; l++) {
    writeln(L[l].MS, ", " , L[l].Prio);
  }          
}

 

#CPLEXOptimizers
#DecisionOptimization

Hi,

in

https://www.linkedin.com/pulse/how-opl-alex-fleischer/

you could read

How to multiply an integer decision variable and a second decision variable ?

regards

#CPLEXOptimizers
#DecisionOptimization