Originally posted by: naveendivakaran

Hi,

I am trying to do Lexicographic/Preemptive Goal Programming using OPL Scripting. I have 15 Goals, and I want to solve one objective at a time and set the optimal value as upper bound for the next iteration and move to next goal. The approach works fine until a certain Goal, and then the solve goes infeasible. If I try to solve the same problem using Weighted Goal Programming approach, the solve does not end up being infeasible. One thing to know is that the model has the numerical problem of scaled infeasibility because of vast differences in the right hand side of constraints. I noticed that If I add a buffer to upper bound on the penultimate Objective before it goes infeasible, I get a feasible solve. 

the mod file looks roughly like this:
minimize(   
            NetObjective
        );
            
subject to
{
  
   //first Objective to minize    
  ctElastic:    
  Obj1 <= infinity;
  
  //3rd objs to minimize    
  ctPain:
  Obj2 <= infinity;
  
  //2nd obj to minimize
  ctBacklog:
  Obj3 <= infinity;
  
   //4th objs to lock    
  ctFGInv:
  Obj4 <= infinity;
  
   //5th objs to lock
  ctObj5:
  Obj5 <= infinity; 
  
  //5th objs to lock
  ctObj6:
  Obj6 <= infinity; 
  
  //NetObjective
  ctNetObj:
  NetObjective 
  -
           
              (Obj1*1 +Obj2 * 0 + Obj3*0 + Obj4*0 - Obj7 * 0  + Obj8 * 0  + Obj9*  0   + Obj10 * 0
            
            + Obj11 * 0    + Obj12* 0 + Obj13*0  + Obj14* 0
            )  == 0;

.
.
.
.
}

//main script

{
....

        cplex.eprhs = 1e-3;
     
        cplex.ppriind = 1;
        cplex.rootalg = 1;
        cplex.scaind = 1;// problem is of the nature of highly varying magnitudes of coefficients and bounds: 1 - 10^~15
    

     thisOplModel.generate();
    
  
    
    
    if(!cplex.solve()) solve_quality = 0;

    
    thisOplModel.ctElastic.UB = thisOplModel.Obj1+1;
    thisOplModel.ctNetObj.setCoef(thisOplModel.Obj1,0);
    
    thisOplModel.ctNetObj.setCoef(thisOplModel.Obj2,-1);
    cplex.ppriind = 1;
        cplex.rootalg = 4;
   
    thisOplModel.ctPain.UB = thisOplModel.Obj2+1;
    thisOplModel.ctNetObj.setCoef(thisOplModel.Obj3,-1);
    
    cplex.ppriind = 1;
        cplex.rootalg = 1; 
    
.....

}
  
Has anybody tried Lexicographic/Preemptive Goal Programming, and had this problem? Can anyone help me solve this problem?

-Naveen

Hi,

instead of

thisOplModel.ctPain.UB = thisOplModel.Obj2+1;

can you try with multiplied by 1.05 ?

Otherwise can you attach the entire model ?

regards

Originally posted by: naveendivakaran

Hi,

Thanks for the suggestion. I will give it a try. To paste the entire problem here is going to be difficult, as I don't think my company policies would allow it. The problem is the problem doesn't occur for all input datasets, but for some. The issue, is the problem has numerical instability/difficulty issues. The upper bound on Objectives ranges between values of magnitude in the order of 10^4 to 10^12. I wonder if by multiplying by 1.05 i might not help the problem, by first of all compromising on optimality, and by still having the numerical instability.  

Hi

and then you could also contact IBM support:

http://www-01.ibm.com/support/docview.wss?uid=swg21507639

regards

Originally posted by: naveendivakaran

Hi Alex,

I tried a different approach. I scaled all the objectives to the same order of magnitude, and while setting an upper bound to the objectives in each iteration, I set it to a rounded number.

i.e for example if i had a problem that yielded optimal values Obj1 = 123, Obj2 = 1231241212, and Obj3 = 12312, in my model, I would set up a scaled_objective decision variable for each objective and I would just have an addition constraint scaled_Obj1 = (Obj1/opt_Obj1*100)+1, where opt_Obj1 is the optimal value achieved in previous iteration, and I would constraint the scaled_Obj1 <= 100; 

This approach worked quite consistently without compromising optimality much.

Thank you for helping out with this.

-Naveen

Hi,

let me add here a tiny example on how to do since I am often asked that.

Suppose you want to position m cells on a n*n 2 dimensions  board.

You have 2 goals:

1) Minimize the max x

2) Minimize the max y

You may do that by using weights. Weights should be computed to make one single objective take into account different objectives:

int n=10;
int m=25;

range position = 0..n-1;

dvar boolean x[position][position];
dvar int obj1 in position;
dvar int obj2 in position;

minimize (obj1)*n+obj2;

subject to
{
  sum(i,j in position) x[i][j]==m;
 
  forall(i,j in position) (x[i][j]==1) => (obj1>=i);
 
  forall(i,j in position) (x[i][j]==1) => (obj2>=j);
}

 tuple sequence_like {
   int start;
   int end;
   string label;
   int type;
 };   
 
 execute
 {
 writeln("objectives : ",obj1+1," ",obj2+1);
 }
 

 

{sequence_like} array2[i in position] = {<j-1,j," ",x[i][j]> | j in position};

 
  execute noname {
    
   array2;
}

And then by clicking array2 you may see

But you may also use a main to do the lexicographic goal programming:

int n=10;
int m=25;

range position = 0..n-1;

dvar boolean x[position][position];
dvar int obj1 in position;
dvar int obj2 in position;

minimize (obj1)*n+obj2;

subject to
{
  sum(i,j in position) x[i][j]==m;
 
  forall(i,j in position) (x[i][j]==1) => (obj1>=i);
 
  forall(i,j in position) (x[i][j]==1) => (obj2>=j);
}

 tuple sequence_like {
   int start;
   int end;
   string label;
   int type;
 };   
 
 execute
 {
 writeln("objectives : ",obj1+1," ",obj2+1);
 }
 
 main
 {
   thisOplModel.generate();
   cplex.setObjCoef(thisOplModel.obj2,0);
   cplex.solve();
   thisOplModel.postProcess();
   var obj1=thisOplModel.obj1.solutionValue;
   thisOplModel.obj1.LB=obj1;
   thisOplModel.obj1.UB=obj1;
   cplex.setObjCoef(thisOplModel.obj2,1);
   cplex.solve();
   thisOplModel.postProcess();
    
 }
 

if you turn

int n=10;
int m=25;

into

int n=100;
int m=250;

you may notice that the goal programming version is 4 times faster than the weight aggregated single objective.

regards

Originally posted by: naveendivakaran

Hi Alex,

I am facing a few additional problems with the lexicographic approach. Basically the problem is due to numerical instability. My decision variables are of highly varying magnitudes. Is there a reason for why you recommended multiplying optimal value of the previous iteration by 1.05 before I set it to upper bound? I would be compromising on optimality if I do that. 

I have 5 iterations in the solve (meaning 5 groups of objectives that I am optimizing and setting upper bound to in subsequent solves). I get vastly varying run times for the same problem (same coefficients and RHS) when I run the solve multiple times, and I also notice that I get different optimals on iterations between replications of the solve. I am using barrier algorithm because that is the best algorithm that can solve the problem fast.

Basically these are the settings that I am using:

    cplex.eprhs = 1e-3; 
    cplex.rootalg = 4;                                     
    cplex.scaind = 1;                                 
    cplex.epmrk = .999;                                       
    cplex.numericalemphasis = true;    

Should I try something else, that can ensure my code would solve the same problem with consistant run time, and consistant solution?