Originally posted by: stevenluda

Hi,

I'm using column generation for a scheduling problem. However, instead of augmenting the restricted master problem(RM) by adding columns, I was adding cuts to the dual of the restricted master(let's say DualMaster), which I believe should be the same in LP case. Thus, each time I'll add a couple of cuts to DualMaster. Each cut is added by using expressions like model.add(expr<=Rhs). Then the DualMaster is solved by setting "cplex.setParam(IloCplex::RootAlg, IloCplex::Dual);", which I believe equals solving the RM. Then after 100 iterations, Error: "IloAlgorithm 000000000DF14D00 cannot change extractables 0 and 22396" jumped out.

What could be the reason for this problem?

Thanks
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: stevenluda

Another information that might help: the error actually happened before starting to solve the master problem, which means it was unable to add some cuts to the model from previous iteration.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: stevenluda

Updates:

As I was debugging the program in VS2010, the previous error disappeared at the iteration where it should jump out. Instead after a few more iterations, the following error came out:
"Error: IloAlgorithm cannot extract extractables 146402 and 146402".

This time the error happened after successfully adding cuts using "model.add()". I assume it failed at the step of "IloCplex cplex(model)".

Hope the information will help.
Thanks
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Can you try to wrap each call to model.add() and cplex.solve() that you suspect to throw the exception into this code:

try 
{ 
// cplex.solve() or model.add() here. ... 
} 

catch (IloAlgorithm::CannotChangeException& e) 
{ std::cerr << 
"CannotChangeException:" << e << std::endl; IloExtractableArray& es = e.getExtractables(); 

for (IloInt i = 0; i < es.getSize(); ++i) std::cerr << 
"  " << i << 
": " << es[i] << std::endl; 

throw; 
} 

catch (IloAlgorithm::CannotExtractException& e) 
{ std::cerr << 
"CannotExtractException:" << e << std::endl; IloExtractableArray& es = e.getExtractables(); 

for (IloInt i = 0; i < es.getSize(); ++i) std::cerr << 
"  " << i << 
": " << es[i] << std::endl; 

throw; 
} 

catch (IloException& e) 
{ std::cerr << 
"IloException: " << e << std::endl; 
// for model.add() print the constraint you just tried to add. ... 

throw; 
}

This should print more details about the exception and should also print the cuts that triggered the exception. What cuts do you see with that?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: stevenluda

Thanks for your help, Dan. I've tried the code, but with those "for" loops commented out in the first two "catch" blocks, because my model would have about 100,000 constraints by the time the error came out. Also, I'm sure that the constraints added are simply linear constraints with 0,1 coefficients.

As I tested the same code on different machines, I noticed that the error showed randomly, but with the following pattern:
Error "cannot change extractables" happens when adding constraints;
Error "cannot extract extractables" happens at the step of "cplex(model)";
And in some recent tests, a third error: cplex out of memory happens when cplex is actually solving the model.

When the three errors happened, the application had pretty much consumed all the memory of the system. So I guess all these errors are due to out of memory.

As mentioned before, by the time the error came out, the LP model has about 100,000 constraints. However, this size is said to take about 100MB for cplex to solve, according to the "Guidelines for estimating CPLEX memory requirements based on problem size". I'm confused why it took almost all the memory. Basically, in my code there are two main problems to solve, master problem and subproblem. The master problem is solved by CPLEX, the subproblem is solved by a label setting algorithm coded myself. The most memory consuming part of the label setting algorithm is a list that dynamically stores all the labels, typically 2,0000 to 4,0000 labels with each taking about 6 bytes, which are all released when subproblem finished. And for the first couple of iterations, I did notice the memory decrease when those labels are freed. The model.add() and cplex(model) were always causing an increase of memory usage shown on the monitor. After a while, the memory kept increasing monotonically, never showed any decrease even at the point where label releasing was carried out.

Since I'm a beginner user of both C++ and CPLEX, I'm totally confused by those information. Hope those details above could provide clues for experts. If there is a need of my code, I'm more than willing to provide.

Thanks
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> stevenluda wrote:
> Thanks for your help, Dan. I've tried the code, but with those "for" loops commented out in the first two "catch" blocks, because my model would have about 100,000 constraints by the time the error came out. Also, I'm sure that the constraints added are simply linear constraints with 0,1 coefficients.
>
The for-loops would have only printed the constraint(s) that triggered the exception. They should not have printed all 100000 constraints.

> As I tested the same code on different machines, I noticed that the error showed randomly, but with the following pattern:
> Error "cannot change extractables" happens when adding constraints;
> Error "cannot extract extractables" happens at the step of "cplex(model)";
> And in some recent tests, a third error: cplex out of memory happens when cplex is actually solving the model.
>
> When the three errors happened, the application had pretty much consumed all the memory of the system. So I guess all these errors are due to out of memory.
>
OK, so the "cannot change" or "cannot extract" might be "out of memory" in disguise.

> As mentioned before, by the time the error came out, the LP model has about 100,000 constraints. However, this size is said to take about 100MB for cplex to solve, according to the "Guidelines for estimating CPLEX memory requirements based on problem size". I'm confused why it took almost all the memory. Basically, in my code there are two main problems to solve, master problem and subproblem. The master problem is solved by CPLEX, the subproblem is solved by a label setting algorithm coded myself. The most memory consuming part of the label setting algorithm is a list that dynamically stores all the labels, typically 2,0000 to 4,0000 labels with each taking about 6 bytes, which are all released when subproblem finished. And for the first couple of iterations, I did notice the memory decrease when those labels are freed. The model.add() and cplex(model) were always causing an increase of memory usage shown on the monitor. After a while, the memory kept increasing monotonically, never showed any decrease even at the point where label releasing was carried out.
>
This smells like a memory leak. You are solving the subproblem in a callback, right? Are you sure you properly release all memory before you return from the callback? In particular all Ilo*Array instances you allocated in the callback.

> Since I'm a beginner user of both C++ and CPLEX, I'm totally confused by those information. Hope those details above could provide clues for experts. If there is a need of my code, I'm more than willing to provide.
>
Could you post the callback code here? Assuming that the algorithm you use for the subproblem has no leaks the problem must be within the callback code.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: stevenluda

Hi, Dan, thanks for your time. Here is a basic structure of my code. I skipped some details because I don't wanna waste too much of your time on that. But if you need them for, I would more than happy to provide. Actually, in a recent check, I improved the whole application and did not encountered those errors mentioned before. But I'm not sure whether the bug I fixed was the only one creating that error. So, here I'll start with the orignial version, followed by debugged version.

The original one is like this:

int main(int, char**) 
{   IloEnv env; 

try 
{ 
// cplex.solve() or model.add() here. define_data(env); IloModel model(env); 

while( Upperbound - Lowerbound > 0.00001 )
{ 
/*********************solve the subproblem ***************************/ 
//here I skipped the details of subproblem codes, since it's too length. There's nothing to do with cplex in this part. 
/************************************************ ***************finished subproblem*************** ************************************************/ 
/*******start adding constraints to model************/ IloExpr expr(env) 
//skipped details of constructing expr in a while loop; 
//add constraint to model model.add(expr < Rhs); 
//end expr  expr.end();   
/*********************release memories of labels*****************************/ 
//here I used free() in a loop to release all labels created by malloc();     
/*********************************************** ***********begin solve master problem************ ************************************************/ IloCplex cplex(model); cplex.setOut(env.getNullStream()); cplex.setWarning(env.getNullStream()); cplex.setParam(IloCplex::RootAlg, IloCplex::Dual); ms_start = clock(); cplex.solve(); 
//skipped details of updating the dual variables needed for subproblem in next iteration             
} 
} env.end(); 

catch()
{ 
//............... 
} 

return 0; 
}

Then, in a recent test, I realized that maybe I should probably end cplex by "cplex.end()" before starting next iteration. So I added cplex.end() after dual variables had been updated.

int main(int, char**) 
{   IloEnv env; 

try 
{ 
// cplex.solve() or model.add() here. define_data(env); IloModel model(env); 

while( Upperbound - Lowerbound > 0.00001 )
{ 
/*********************solve the subproblem ***************************/ 
//here I skipped the details of subproblem codes, since it's too length. There's nothing to do with cplex in this part. 
/************************************************ ***************finished subproblem*************** ************************************************/ 
/*******start adding constraints to model************/ IloExpr expr(env) 
//skipped details of constructing expr in a while loop; 
//add constraint to model model.add(expr < Rhs); 
//end expr  expr.end();   
/*********************release memories of labels*****************************/ 
//here I used free() in a loop to release all labels created by malloc();     
/*********************************************** ***********begin solve master problem************ ************************************************/ IloCplex cplex(model); cplex.setOut(env.getNullStream()); cplex.setWarning(env.getNullStream()); cplex.setParam(IloCplex::RootAlg, IloCplex::Dual); ms_start = clock(); cplex.solve(); 
//skipped details of updating the dual variables needed for subproblem in next iteration      
//end cplex cplex.end(); 
} 
} env.end(); 

catch()
{ 
//............... 
} 

return 0; 
}

In this case, no previous errors showed up before I terminate the application manually. SBut still, the memory usage came to a high level after the master problem acummulated nearly 1 million contraints, and the time for solving master problem greately prolonged.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: stevenluda

It seems to me that if missing "cplex.end()" in the while loop, the application would create another "cplex" and extract the model to solve while the "cplex" created in previous iteration still exist. Is it the case?

Moreover, if I add "cplex.end()", in the next iteration, does cplex solve the problem all from scratch or start with the basis in previous iteration? Since I'm using dual simplex and only adding a few columns to the dual problem, the second case may save a lot of time.

Thanks
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: stevenluda

Updates:

As I studied the cutting stock example provided with cplex, it seems that a better way is to put "IloCplex cplex(model)" and the parameter settings outside the while loop instead of adding "cplex.end()" at the end of each iteration. In this way, it runs faster and use less memory. But I'm still not sure how cplex re-optimizes when new constraints added. To be specific, since the algorithm is set to dual simplex, I think cplex should solve the dual problem each time with new columns added. My questions is does cplex solve the dual problem from scratch or start with the optimal basis from previous iteration?

Also, I'm wondering if there is an easy way to initiate or reset arrays to some special form, for example having all ones and all zeros as the input.

Many appreciations
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Trying to answer all 3 previous posts in one shot:
1. Missing the call to cplex.end() was definitely a memory leak. Adding this call will save lots of memory.
2. If you solve the same model repeatedly then it is preferable to use the same IloCplex instance for each solve. That means you should instantiate IloCplex outside the loop. Note that in this case you don't have to re-extract the full model every time. Once you have done 'IloCplex cplex(model)' the IloCplex instance will be automatically informed about any changes to make to 'model'.
3. CPLEX tries hard to use information from previous solves to jump start a solve on a modified model. If you just add a row to the model and select the dual simplex then CPLEX should be able to start from the dual basis of the previous step.
4. I am not sure whether I got your question about arrays correct: You want to set all slots in the array to the same value? Are you talking about instances of IloArray or plain arrays? for IloArrays I think there is no function to do that. For plain arrays you could use memset. That at least works to set arrays to all 0 (and assuming that integers are stored as 2's complement also to set all entries in an integer array to -1).
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: stevenluda

Many thanks for the help.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: stevenluda

Hi Dan,

In a recent test, I tried to formulate my master problem in terms of adding columns, so that finally I could easily convert the problem to an IP problem by using "IloCoversion(env, var, ILOINT)". However, the application consumed far more memory when running (almost 3 times more than my previous application that adds cuts and solves the dual). Do you think that was due to another memory leak? I was tracking the number of columns or cuts added in both applications, the numbers were close at each iteration.

the structure of the new code is like this:

int main(int, char**) 
{ IloEnv env; 

try 
{ 
// cplex.solve() or model.add() here. define_data(env); IloModel model(env); IloNumVarArray Var(env); IloObjective Objetive = IloAdd(model,IloMinimize(env)); IloRangeArray ConstraintSet1 = IloAdd(model, IloRangeArray(env,nb1,1,IloInfinity)); IloRangeArray ConstraintSet2 = IloAdd(model, IloRangeArray(env,nb2, 0, 1));   
//skipped adding initial columns and var to model IloCplex cplex(model); cplex.setOut(env.getNullStream()); cplex.setWarning(env.getNullStream()); 

while( Upperbound - Lowerbound > 0.00001 )
{ 
/*********************solve the subproblem ***************************/ 
//here I skipped the details of subproblem codes, since it's too lengthy. There's nothing to do with cplex in this part. 
/************************************************ ***************finished subproblem*************** ************************************************/ 
/*******start adding columns to model************/ 
//add constraint to model Var.add(IloNumVar());   
/*********************release memories of labels*****************************/ 
//here I used free() in a loop to release all labels created by malloc(); 
/*********************************************** ***********begin to solve master problem************ ************************************************/ cplex.solve(); 
//skipped details of updating the dual variables needed for subproblem in next iteration           
} 
} env.end(); 

catch()
{ 
//............... 
} 

return 0; 
}

Thanks
#CPLEXOptimizers
#DecisionOptimization