Originally posted by: Christin1991

Hello,

I am currently trying to implement the " Subgradient Method" to get the "Lagrange multiplier" for the "Lagrange Relaxation".

I used the example of the "Lagrange Relaxation" given from IBM/opl/examples. I want to use it for only upper bounds, but started with an simple example of relaxing equality constraints given in a book.

Unfortunatley I don't get the right results. I think that the mistake is, that CPLEX isn't using the current decisionsvariables for updating slack, but I don't know how to access them.

I would be very thankful for any help or correction of my code.

Furthermore I would like to kindly ask, how to get the UpperBound of a problem. The thing is, that my intention is to use this process to get the Lagrange Multiplicator for my large scale mixed integer linear Problem with a lot of indices and a lot of variables. I am not sure yet, how to get the Upper Bound of this large scale problem.

Best regards,

Christin

Originally posted by: Christin1991

Hello,

i will try to put it into other words :

i am trying to implement the subgradient method to get the lagrange multiplicator for my difficult constraint, which i would like to relax. For implementing the basic programm, i used an simple example :

dexpr float objective = sum (i in iset,j in jset) (c[i,j] * x[i,j]);

subject to

{
  forall(i in iset)
      {
    constraint1[i] : sum(j in jset) x[i][j] == 1;
      }
      
  forall ( j in jset )
    {
    constraint2[j]: sum(i in iset) C[i][j] <= d[j];
      }    
 

I want to realx constraint 1 now to get this model to solve (P2):

dexpr float objective = sum (i in iset,j in jset) (c[i,j] * x[i,j])+ sum (i in iset)(mult[i]* sum(j in jset)(1-x[i,j]));
minimize objective;

subject to

{   
  forall ( j in jset )
    {
    constraint2[j]: sum(i in iset) C[i][j] * x[i][j]<= d[j];
      }    
 
 }
 . Now I want to use the Subgradient Method to get my Lagrange Multiplier: "mult[i]".

By applying the subgradient method, i get the wrong values for updating slack. Slack should get the value of the constraints of the current iteration. The value of the current constraints are calculated by using the current Lagrange Multiplier and to optimize (P2) to get new deicison variables in every iterations. This new decision variables are used to get the value of the contraint.

if (m3Cplex.solve())    
          
            {
            var sum = new Array ( thisOplModel.iset);
            var Lagrangian;
           Lagrangian = m3Cplex.getObjValue();
   

            for ( var i in thisOplModel.iset)
              {
                for (var j in thisOplModel.jset)
              
                    sum [i]+= m3.x[i][j];
            
              slack[i] = 1 - sum[i] ;
              }   
           }      

The problem is, that the decision variables stay zero and slack keep being 1. So there must be a mistake in my code.

Other relevant definitions for the foor loop are:

         var m3Source = new IloOplModelSource("UpperBound.mod");
         var m3Cplex = new IloCplex();
         var m3Def = new IloOplModelDefinition(m3Source);
         
          // model used to retrieve data common at each iteration
          var m3_init = new IloOplModel(m3Def,m3Cplex);
          m3_init.addDataSource(data);
          var dataMult = new IloOplDataSource("mult.dat");
          m3_init.addDataSource(dataMult);
         m3_init.generate();
          var data3 = m3_init.dataElements;
 
      // initialize arrays and variables used in the loop that follows
      var same = 0;
      var same_limit = 3;
     var slack = new Array(thisOplModel.iSet);

var m3 = new IloOplModel(m3Def,m3Cplex);
        for (i in thisOplModel.iset)
            {
              data3.mult[i] = mult[i];
            }
        m3.addDataSource(data3);  
        m3.generate();

Since x[i,j] continues to be zero, I think that there is a mistake by solving the right current (P2) and getting it's decision variables.

I am very thankfull for any kind of help !

Best regards,

Christin

Hi

instead of

var data3 = m3_init.dataElements;
 
      // initialize arrays and variables used in the loop that follows
      var same = 0;
      var same_limit = 3;
     var slack = new Array(thisOplModel.iSet); var m3 = new IloOplModel(m3Def,m3Cplex);
        for (i in thisOplModel.iset)
            {
              data3.mult[i] = mult[i];
            }
        m3.addDataSource(data3);

Why do not you write something like

var data3= new IloOplDataElements();
 
  for (i in thisOplModel.iset)
            {
              data3.mult[i] = mult[i];
            }
 
 
  m3.addDataSource(data3);

?

regards

Originally posted by: Christin1991

Hello,

thank you for your quick answer!

I can't creat a new DataElement with data3, because i need the elements saved in m3_init.dataElements from my original model. My aim is to solve here

if (m3Cplex.solve())    
          
            {
            var sum = new Array ( thisOplModel.iset);
            var Lagrangian;
           Lagrangian = m3Cplex.getObjValue();
   

            for ( var i in thisOplModel.iset)
              {
                for (var j in thisOplModel.jset)
              
                    sum [i]+= m3.x[i][j];
            
              slack[i] = 1 - sum[i] ;
              }   
           }     

always the same model, but with a different "mult ", which i changed in my data elements just before the solving process and to get new resulting decisionvariable values for x ( to update my slack). I think that I'm not accessing the right results of the decisionvariable x[i,j] because it's always zero though my objective is changing.

best regards,

Christin

Hi

so if you need data3, you may use

var data3b= new IloOplDataElements();
 
  for (i in thisOplModel.iset)
            {
              data3b.mult[i] = mult[i];
            }
 
 
  m3.addDataSource(data3b);

regards

PS:

I gave some examples at

https://www.ibm.com/developerworks/community/forums/html/topic?id=df612d06-4c0a-4873-b655-42b66422e733&ps=25

Originally posted by: Christin1991

Hey

thank you for your answer.

The thing is, that in data3 are all parameters for my mathematical programm saved. There is only one parameter ( the langrangian multiplier "mult[i]") which i update in every iteration in data3. The other parameters stay the same and have to be included in data3, because for optimizing my model, i need the information of all parameter(including the old constant ones, and the changing parameter mult). So i think that i can't write a new dataelement because i need to rewrite the old one. Or is there a mistake in my thinking? I mean obviously there is some mistake in my code, but i can't find it since a week now.

thank you for your help!

best regards christin

Hi,

with the same model you may  use new IloOplDataElements(); and IloOplDataSource.

Let me share an example with an IloOplDataSource

sub.mod

{float} maxOfx = ...;

dvar float x;

 

maximize x;

subject to{

x<=max(i in maxOfx)i;

}

sub.dat

maxOfx=

{10

};

then

main{

var source = new IloOplModelSource("sub.mod");

var cplex = new IloCplex();

var def = new IloOplModelDefinition(source);

var opl = new IloOplModel(def,cplex);

var data = new IloOplDataSource("sub.dat");

opl.addDataSource(data);

opl.generate();

if (cplex.solve()) {

writeln("OBJ = " + cplex.getObjValue());

} else {

writeln("No solution");

}

var opl2 = new IloOplModel(def,cplex);

var data2= new IloOplDataSource("sub.dat");

 

opl2.addDataSource(data2);

opl2.dataElements.maxOfx.add(20.0);

opl2.generate();

 

if (cplex.solve()) {

writeln("OBJ = " + cplex.getObjValue());

} else {

writeln("No solution");

}

 

opl.end();

opl2.end();

data.end();

def.end();

cplex.end();

source.end();

}

gives

OBJ = 10

OBJ = 20

regards

Originally posted by: Christin1991

Thank you for you answer, I think I understand now what you mean.

But I guess, that the mistake in my problem is not updating mult[i] , it's has to do something with the calculationof  the optimal values und decision variables. Because if i look at the scripting, the updating von mult[i] seems to work, just that it gets the wrong values. It seems to me that it its always optimizing with new mult[i]-values but gets the wrong decision variables.

Originally posted by: ueve.fr-P.hD-Tong

Hi Alex,

I've seen many of your answers, and I believe you are really professional in Cplex OPL, and I got a problem in coding the Vheicle routing subtour elimination constraints, would you please give me some suggestions?

the attach is my constraints, and the opl code for Tsp( travelling sales man problem). I tend to modify the tsp code so that it fits my problem, do you have any idea, thank you in advance!

best regards

Tong

Originally posted by: ueve.fr-P.hD-Tong

HI dear all,

Does anyone has the code of VRP in OPL?

I encounter some difficulties in coding the constraints in the picture, I appreciated a lot that any one can give me some code example or suggestions on coding the vehicle routing subtour elimination constraints in OPL language?

thank you in advance!

Best regards

Tong