Originally posted by: Allexandre

Hi,

I'm developing a mathematical model for Vehicle Routing Problem. As I decomposed it using the Dantzig-Wolfe method, for solve the precification subproblem I need to get the dual values from my two constraints from Master Problem,

In my master problem I have

mpe is a MP object where I will create the model.

mpe.constraints = IloRangeArray(env);

....

mpe.constraints.add(1 <= rConv <= 1);

......

mpe.constraints.add(r4 >= 1);

....

mpe.mod.add(mpe.constraints); //where I add the constraints r4 (which has a domain) and rConv.

When I deliver the mpe object to the function where I will solve the Subproblem, how can I get the dual values from mpe.constraints?

Thanks a lot.

Function IloCplex::getDuals(IloNumArray, IloRangeArray) returns the dual values for all constraints in the passed range array. So invoking that function with mpe.constraints as argument should give you the duals.

Originally posted by: Allexandre

Hi Daniel,

I tried this one and the IloCplex::getDual, but I'm not achieving the right constraint to the right parameter. I showing to you my code, can you help me?

//Sub Problem Objective Function
void cg_sp_create_model(DAT &d, SP_CPX_DAT &spe){ //Ok na criação

  IloEnv env = spe.cplex.getEnv();
  spe.x = IloNumVarArray(env, d.n3, 0.0, 1.0, ILOINT);
  spe.pi_ = IloNumArray(env, d.n); 
  spe.constraints = IloRangeArray(env);

  // ===============
  // função objetivo
  // ===============
  IloExpr spfoe(env);
  for (int i = 0; i <= (d.n-1); i++){      
    for (int j = 1; j <= d.n; j++){                
      if(i != j){                             
        if (!((i == 0) && (j == d.n))){               
          if(i != 0){
            for (int o = 1; o <= (d.Q - d.oferta[j]); o++){ 
              if (j != d.n){
                //sum{(i,j,o) in Ac: j in Vplus}(-pi_j[j])*x[i,j,o]
                spfoe += (-spe.pi_[(j-1)]) * spe.x[d.n*d.Q*(i) + d.Q*(j-1) + (o)];
              }
              else{
                //sum{(i,0,o) in Ac}(c[i,0,o])*x[i,0,o]
                spfoe += d.c[i][j]*spe.x[d.n*d.Q*(i) + d.Q*(j-1) + (o)];
              }
            }
          }
          else{      // i == 0 and o == 0 
            spfoe += (-spe.pi_[(j-1)]) * spe.x[d.n*d.Q*(i) + d.Q*(j-1) + (0)];
            //union {(i,j) in A, o in 0..0: i = 0}
          }
        }
      }
    }
  }
  spfoe -= spe.pi0_;    // -pi_0
  spe.fo = IloAdd(spe.mod, IloMinimize(env, spfoe));
  spfoe.end();
  
  //restriction omitted
  
  //HERE: The item spe.pi_ and spe.pi0_ will receive the dual from the constraints from the master problem below
  
  //==============================================
  
  
    //==============================================

  //===================
  // Objective Function Declaration for Master Problem Omitted
  //========================
  
//constraint rConv
IloExpr rConv(env);
  for (int r = 1; r <= d.R; r++){
    rConv += mpe.lambda[(r-1)];
  }
  mpe.constraints.add(1 <= rConv <= 1);
  rConv.end(); 
  
  //Constraint r4
  for (int j = 1; j <= (d.n-1); j++){             
    IloExpr r4(env);
    for (int i = 0; i <= (d.n-1); i++){   
      if(i != j){                            
        for(int r = 1; r <= d.R; r++){
          if(i != 0){
            for (int o = d.oferta[i]; o <= (d.Q - d.oferta[j]); o++){
              //sum{(i,j,o) in Ac, r in 1..R: o in 0..(C-o_i[j])} q_[i,j,o,r]*lambda[r]
              r4 += mpe.q[d.n*d.n*d.Q*(r-1) + d.n*d.Q*(i) + d.Q*(j-1) + (o)]*mpe.lambda[r-1];
            }
          }
          else{//i == 0 and o == 0
            //sum{(i,j,o) in Ac, r in 1..R: o in 0..(C-o_i[j])} q_[i,j,o,r]*lambda[r]
            r4 += mpe.q[d.n*d.n*d.Q*(r-1) + d.n*d.Q*(i) + d.Q*(j-1) + (0)]*mpe.lambda[r-1];
          }
        }
      }
    }
    //+ e >= 1
    r4 += mpe.e;
    mpe.constraints.add(r4 >= 1);
    r4.end();
  }
  //*/
  
 
  mpe.mod.add(mpe.constraints);
  
  //================================================================
  
  //when I create a method to solve the SP, I want spe.pi_ and spe.pi0_  to receive the dual from the constraints from the master problem
  
  //Here is how I'm doing
 
  spe.pi0_ = mpe.cplex.getDual(mpe.constraints[0]);
  //mpe.cplex.getDuals(spe.pi0_,mpe.constraints[0]);
  for (int j = 1; j <= (d.n-1); j++){
    spe.pi_[j] = mpe.cplex.getDual(mpe.constraints[j]);
    //mpe.cplex.getDuals(spe.pi_, mpe.constraints);
  }
  //*/

The messa shown is: Error: CPLEX Error  1217: No solution exists.

Thanks!

Error "no solution exists" usually has one of the following three causes

1. You did not call cplex.solve() before calling cplex.getDuals()
2. You did call cplex.solve() but did modify the problem before calling cplex.getDuals() (modifying the problem invalidates the solution)
3. Your problem is infeasible (in that case cplex.solve() would have returned false)

Can you please check if any of the above happens in your code?

Originally posted by: Allexandre

Hi Daniel,

1) Yes, I really wasn't calling cplex::solve() before take the duals;

2) As I didn't call .solve(), I also didn't modify the problem.

The message that is now shown is: Error: IloExtractable 722 IloNumVarI has not been extracted by IloAlgorithm 0x5fd32e0

Looks like you are invoking getDuals() or getValues() on a variable that is not part of your model.

Either do not call those functions for variables that are not in the model or explicitly add those variables via IloModel::add() to the model.

Originally posted by: Allexandre

spe.pi0_ = mpe.cplex.getDual(mpe.constraints[0]);
for (int j = 1; j <= (d.n-1); j++){
    spe.pi_[j] = mpe.cplex.getDual(mpe.constraints[j]);
}

Above is the way thar I try to get the dual value from mpe.constraints[index] that I added to the model (line 89). I understood that I can't call these functions for variables that aren't in the model, but these variables are the dual ones (that references mine mpe.contraints)?

Thanks

Hm, at first glance that code looks good. Did you modify mpe.constraints (add or remove constraints) after adding it to the model?

Originally posted by: Allexandre

Hi Daniel,

No, I don't modify. I split my code in this way:

1. Create the Sub Problem Model, where I add the objective function of Dantzig-Wolfe subproblem (DWSP - Pricing) and its constraints.
2. Create the Column Generation  where I add the objective function of Dantzig-Wolfe subproblem (DWSPe - Pricing) and its constraints,
3. Create the Dantzig-Wolfe Master Problem (DWMP) with Column Generation, and one of the variables is an ERROR, that I minimize. here I add the OF and model constraints;
4. Create the Dantzig-Wolfe Master Problem  and one of the variables is an ERROR, that I minimize. here I add the OF and model constraints;
5. Solve the DWSP, the code below shows its code;
6. Solve the DWMP;

The function solve_sp, I use to solve either DWSP or the DWSPe;

void solve_sp(DAT &d, SP_CPX_DAT &sp, MP_CPX_DAT &mp){
  IloEnv env = sp.cplex.getEnv();
  
  sp.cplex.solve();
  
  sp._fo = sp.cplex.getObjValue();
  
  if(sp.cplex.getStatus() != IloAlgorithm::Optimal){
    cout << "Error Subproblem" << endl;
    exit(1);
  }
}//end solve_sp

Thanks!

If I understand correctly then you have multiple instances of IloCplex in your code?

Is it possible that you are mixing them in a bad way? Is it possible that you call getDual(mpe.constraints[j]) on an IloCplex instance that did not solve a model containing mpe.constraints?

Originally posted by: Allexandre

Hi Daniel, 

I had few progress, but I found the local where I have the  Error: IloExtractable 722 IloNumVarI has not been extracted by IloAlgorithm 0x5fd32e0

It is this piece of code:

double solve_sp(DAT &d, MP_CPX_DAT &mp, SP_CPX_DAT &sp){
  IloEnv env = sp.cplex.getEnv();
  sp.cplex.solve();
  sp._fo = sp.cplex.getObjValue();
  
  //sp.cplex.getValues(sp.x_,sp.x);
  
  for (int i = 0; i <= (d.n-1); i++){      
    for (int j = 1; j <= d.n; j++){                
      if(i != j){                             
        if (!((i == 0) && (j == d.n))){               
          if(i != 0){
            for (int o = 1; o <= (d.Q - d.oferta[j]); o++){ 
              cout << "i=" << i << ", j=" << j << ", o=" << o << endl;
              getchar();
              sp.x_[d.n*d.Q*(i) + d.Q*(j-1) + (o)] = sp.cplex.getValue(sp.x[d.n*d.Q*(i) + d.Q*(j-1) + (o)]);
              cout << "x[" << i << ", " << j <<", "<< o <<"] = " << sp.x_[d.n*d.Q*(i) + d.Q*(j-1) + (o)] << endl;
              //{(i,j) in A, o in 0..C: i != 0 and o + o_i[j] <= C and o > 0} 
            }
          }
          else{      // i == 0 and o == 0 
            //cout << i<<", "<<j<<", "<< 0 << endl;
            //getchar();
            sp.x_[d.n*d.Q*(i) + d.Q*(j-1) + (0)] = sp.cplex.getValue(sp.x[d.n*d.Q*(i) + d.Q*(j-1) + (0)]);
            cout << "x["<<i<<", "<<j<<", "<< 0 <<"] = " << sp.x_[d.n*d.Q*(i) + d.Q*(j-1) + (0)] << endl;
            //union {(i,j) in A, o in 0..0: i = 0}
          }
        }
      }
    }
  }
  //*/
  if(sp.cplex.getStatus() != IloAlgorithm::Optimal){
    cout << "Error Subproblem" << endl;
    exit(1);
  }
  else{
    cout << "SP is optimal!, FOSP = " << sp._fo << endl;
  }
  //*/
  return 0.0;
}

When my indexes are i=1, j=2, o=1 (first time inside for (int o = 1; o <= (d.Q - d.oferta[j])) it returned this error. On the model, I declare in this way:

void cg_sp_create_model(DAT &d, SP_CPX_DAT &spe){

  IloEnv env = spe.cplex.getEnv();
  spe.x = IloNumVarArray(env, d.n3, 0.0, 1.0, ILOINT);
  spe.x_ = IloNumArray(env, d.n3);
  spe.pi_ = IloNumArray(env, d.n);
  spe.constraints = IloRangeArray(env);


  IloExpr spfoe(env);
  for (int i = 0; i <= (d.n-1); i++){             
    for (int j = 1; j <= d.n; j++){               
      if(i != j){                            
        if (!((i == 0) && (j == d.n))){              
          if(i != 0){
            for (int o = 1; o <= (d.Q - d.oferta[j]); o++){ 
              if (j != d.n){
                //sum{(i,j,o) in Ac: j in Vplus}(-pi_j[j])*x[i,j,o]
                spfoe += (-spe.pi_[(j-1)]) * spe.x[d.n*d.Q*(i) + d.Q*(j-1) + (o)];
              }
              else{
                //sum{(i,0,o) in Ac}(c[i,0,o])*x[i,0,o]
                spfoe += d.c[i][j]*spe.x[d.n*d.Q*(i) + d.Q*(j-1) + (o)];
              }
            }
          }
          else{      // i == 0 and o == 0 
            spfoe += (-spe.pi_[(j-1)]) * spe.x[d.n*d.Q*(i) + d.Q*(j-1) + (0)];
            //union {(i,j) in A, o in 0..0: i = 0}
          }
        }
      }
    }
  }
  spfoe -= spe.pi0_;    // -pi_0
  spe.fo = IloAdd(spe.mod, IloMinimize(env, spfoe));
  spfoe.end();

Why there is a variable x, I think it is empty, if in its declaratio, x should be 0 or 1??

Thanks a lot!

Originally posted by: Allexandre

HI,

I think I became few confused. So, this Error above, I solved, It ocurred due a constraint is only for d.oferta[i] <= o <= (d.C - d.oferta[j], and I have to add this when I'm transfering from x_[i,j,o] to q[r,i,j,o]. 

Now, returning to the initial question: The right way to catch dual values from constraints in Master Problem to parameters in Sub-problem. 

Below, is the piece of my code where I add the constraints (in Master Problem) that I will take the dual values (in Sub-Problem)

//rConv: sum{r in 1..R}lambda[r] = 1
  IloExpr rConv(env);
  for (int r = 1; r <= d.R; r++){
    rConv += mpe.lambda[(r-1)];
  }
  mpe.constraints.add(1 <= rConv <= 1);
  rConv.end();  
  
  //cout << "R4" << endl;
  // =====================================================================================================
  //s.t. r1pm{j in Vplus}: sum{(i,j,o) in Ac, r in 1..R: o in 0..(C-o_i[j])} 
  //                                            q_[i,j,o,r]*lambda[r] + e >= 1;
  //garante que todo nó usuário esteja conectado
  // =====================================================================================================
  //set Ac := {(i,j) in A, o in 0..C: i != 0 and o + o_i[j] <= C and o > 0} union {(i,j) in A, o in 0..0: i = 0};
  for (int j = 1; j <= (d.n-1); j++){             //percorrendo os nós usuários
    IloExpr r4(env);
    for (int i = 0; i <= (d.n-1); i++){           //percorrendo os nós, inclusive depósito
      if(i != j){                            //se os nós i e j são diferentes
        for(int r = 1; r <= d.R; r++){
          if(i != 0){
            for (int o = d.oferta[i]; o <= (d.Q - d.oferta[j]); o++){
              //sum{(i,j,o) in Ac, r in 1..R: o in 0..(C-o_i[j])} q_[i,j,o,r]*lambda[r]
              r4 += mpe.q[d.n*d.n*d.Q*(r-1) + d.n*d.Q*(i) + d.Q*(j-1) + (o)]*mpe.lambda[r-1];
            }
          }
          else{//i == 0 and o == 0
            //sum{(i,j,o) in Ac, r in 1..R: o in 0..(C-o_i[j])} q_[i,j,o,r]*lambda[r]
            r4 += mpe.q[d.n*d.n*d.Q*(r-1) + d.n*d.Q*(i) + d.Q*(j-1) + (0)]*mpe.lambda[r-1];
          }
        }
      }
    }
    //+ e >= 1
    r4 += mpe.e;
    mpe.constraints.add(r4 >= 1);
    r4.end();
  }
  //*/
  
  mpe.mod.add(mpe.constraints);

And now, inside a looping which solves the SP and MP, how I try to catch the duals:

spe.pi0_ = mpe.cplex.getDual(mpe.constraints[0]);
//cout << "pi0 = " << spe.pi0_ << endl;
for (int j = 1; j <= (d.n-1); j++){
    spe.pi_[j] = mpe.cplex.getDual(mpe.constraints[j]);
    //cout << "pi[" << j << "] = "<< spe.pi_[j] << endl;
}

I thought that mpe.constraints[0] stores the dual value from rConv, and mpe.constraints[(j-1)] stores for each j in r4. Is that right?

Thanks a lot.

As far as I can tell you are right: Provided that mpe.cplex solved mpe.mod the dual for "rConv == 1" should be mpe.cplex.getDual(mpe.constraints[0]) and the duals for r4 should also be as you describe them. Do you still get exceptions?

Originally posted by: Allexandre

No, now I'm not catching any exception. I just wanna know if that way was right. Thanks a lot. 

I belive that the last problem that I'm facing is how to change the coeficients from constraints in my master problem. Inside this MP, The objecive function is minimize an error e and its constraints have a coeficient q which I take from my subproblem.

Thanks.