Originally posted by: SystemAdmin

I am trying to write a simple linear cutting plane method that adds feasibility constraints at every iteration. The problem is a relaxation of the MIP problem and I can get it to solve but it is slower than the MIP equivalent and takes significantly more memory which makes me think I have an error in the way I programmed it. The basic method is as follows, recall this is just an example so it won't compile and syntax does not matter.

IloEnv env;

IloModel model(env);

model.add( IloMinimize(env, /* linear obj */ ) );

model.add( /* initial linear constraints */ );

IloCplex cplex(model);

while(!solved)
{
if(!cplex.solve()){
throw(-1);
}

// get solution

if( !feasible){
model.add( /* linear feasibility constraint */);
}else{
// done
}
}

This methodl works but it is very inefficient on larger problems and seems to have a memory leak. If I move the initilization of IloCplex inside the while loop it gets even worse. If i changed model.add( /* constrant */) to cplex.addUserCut it complains that is not a MIP and I don't want to use a MIP becuase this is not a MIP it is an LP. Where am I going wrong? What is wrong with this approach?
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

I don't see anything wrong with your framework. You might want to experiment with the RootAlg parameter (which selects the simplex version). The default value (let CPLEX choose) probably leads to CPLEX choosing dual simplex, which probably is the best choice, but it can't hurt to experiment.

If there's a memory leak, it may be due to the way that you construct the extra constraints (which we can't tell from the framework you posted).

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Thanks for your response. I could link to my github which has the code for the constraints but I think it would require you to sift through too much code to get an understanding of it. This is what I do essentially.

model.add( foo(env, /* other arguments) <= /* some constant in the form of an IloNum */ );

Where foo(env, ...) returns an IloExpr so.

IloExpr foo(IloEnv env, /** other arguments */ );

I can't call IloExpr::end() on this expression because the scope is inside the mode.add()
function call so I figured I wouldn't have and the destructor would take care of deallocation.
Correct me if I am wrong.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

I use Java, where memory management is civilized, so I may be the wrong person to answer this. That said, I'm pretty sure you do not want to end the output of foo, because that would (I think) delete it from the model.

Since you are adding a constraint in each pass, and never deleting constraints, the memory footprint will obviously grow. Do you have evidence that you are leaking memory beyond the expected increased use?

Also, have you tried adding constraints as lazy constraints? It would not affect memory use, but if your cutting planes tend to become non-binding when more cuts are added, it might help with execution time.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

The evidence I have is programming the equivalent MIP and having it use significantly less memory. I have also saved the model as an *.lp file then imported it in a new program and solved that iteration and it takes minimal memory. When I say my cutting plane method is taking too much memory I mean I am running out of memory on my computer. It is taking over 6GB. While loading in the *.lp file and solving it takes less than 100MB. Of course the memory could leak could be on my side but I highly doubt it because I do no dynamic memory allocation outside of getting the initial data for the problem. Other evidence I have is the there are 8500 decision varibales and at iteration k there are at most 2*k constraints. So if I just consider how much memory would it take to store 8500*2*k doubles it is barely anything. Not that cplex needs more memory than just that but I doubt it needs on the order of 20 times that much.

I haven't tried lazy constraints, but I did seem them. I could give it a shot.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

> 3TSV_Nolan_Sandberg wrote:
> I have also saved the model as an *.lp file then imported it in a new program and solved that iteration and it takes minimal memory. When I say my cutting plane method is taking too much memory I mean I am running out of memory on my computer. It is taking over 6GB. While loading in the *.lp file and solving it takes less than 100MB.

Does your LP file include the same number of added constraints (cutting planes) as you have when you run out of memory with the cutting plane method?

You could try a tool like Valgrind to pin down where memory is leaking.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Yes, the LP has the same constraints. I was actually do it wrong before you mentioned it as I never extracted the model after importing, but it made no difference. It can still solve this problem easily.

I also found this while browsing IBM's website. http://www-01.ibm.com/support/docview.wss?uid=swg21399933. It says for LP the amount of memory used to solve should be number of constrants/1000 to get megabytes used to solve the problem considering I only get to about 5k constraits I should be using no where near the amount of memory I am.

I'm on windows so I would have to find a windows equivalent to Valgrind.

Thanks, I'm going to keep browsing my code to see what the problem is. I'll post if I figure it out.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

I have some more info. IloEnv has a member function called getMemoryUsage() which returns the bytes used and getMaxId() which returns the amount of extractables.

at certain iterations I have the following.

Iteration Constraints MB Extractables
1 2 7 25088
100 175 381 1058909
200 375 737 2084139
300 520 1080 3031070
400 720 1758 4907632

As you can see the memory usage is increasing very quickly. There must be something wrong with the way I am adding them.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

My guess is that you are leaking memory in foo() because you are missing calls to end() in some places. Can you try to use IloEnv::getMemoryUsage to try to see whether you consume an unreasonable amount of memory in foo()?
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

I think this is what is happening, too. I think I just link what foo() actually is because the code is not long.

IloExpr twelveLHS(IloEnv & env, Sparse_Matrix<IloInt>& vox, vector<unsigned int> & A,
IloNum Tx, vector<unsigned int> & X, IloNumVarArray& w)
{
IloExpr expr(env);

for(unsigned int i=0;i<A.size();++i)
{
expr += D(A[i], vox, w, env) - Tx;
}

return expr;
}

And D(...) is the following function.

IloExpr D(unsigned int i, Sparse_Matrix<IloInt>& vox, IloNumVarArray& w, IloEnv & env)
{
IloExpr exp(env);

for(unsigned int j=vox.ia[i];j<vox.iai+1;++j)
{
exp += vox.a[j]*w[vox.jaj];
}

return exp;
}

The only problem I could see with this is that you cannot return a IloExpr like this because it doesn't deallocate somehow. If the C++ bindings for cplex were programming to not allow this method of programming I think it would be rather foolish. If this is not acceptable then I could just pass in the IloExpr as an argument by reference. Do I always have to call the end of an IloExtractable? Shouldn't the destructor deallocate the memory when the scope of the variable is left?
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

All the extractable objects that you create are actually handle classes. They simply store a handle to an implementation class. The instance of the implementation class is not deleted in the destructor of the handle. A very short description of this concept can be found here.

I think you need to explicitly call end() on the instances of IloExpr that you create.
So you need to turn

model.add(foo(...) <= RHS);

into

IloExpr expr = foo(...); model.add(expr <= RHS); expr.end();

The "problem" here is that some of the Concert classes are passed around by reference and some are passed around by value. IloExpr is passed by value, so passing it to IloModel::add() will create a deep copy of the expression.
I fully agree that this results in rather unexpected behavior :-(
You can find more details about this in the Creation of extractable objects in the user manual.
I hope this gives you an idea how to fix this leakage.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Did I hear someone mention the word "Java"? :-)

Paul
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Haha, I'm in too deep with C++. Using multiple libraries and I don't know java.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

You were right Daniel. Significantly faster and taking about 1/10th the memory for the same number of constraints. I really appreciate the help.

I do think the way the c++ is designed in this matter is peculiar. The user has no idea that he has done dynamic allocation but yet he can easily create memory leaks. The only I could see to delete this extractables I created is iterate through all the extractables in IloEnv and find them. I have no idea how you would know which are the correct ones though.

Again, thanks for your help.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Obviously there is not much that I can say in defense of Concert memory management here :-(
The design is very old and dates back to the days when C++ was still young.
The most "problematic" class in this context is IloExpr. Here are some things that I usually do to avoid problems:
1. Don't return IloExpr from functions. Instead pass a reference to the expression that is supposed to receive the result. That is, instead of

IloExpr expr = function(...);

do

IloExpr expr(env); function(..., expr); ... expr.end();

That way it is explicitly clear were the expression is allocated and deallocated.
2. Try to avoid using operator+ etc. to build expressions. Instead use operator+= etc. whenever possible. This is much faster and makes it explicit that no new objects are allocated.
3. Sometimes I wrap IloExpr into a class that does proper RAII so that objects get destroyed when they go out of scope.

class RAIIExpr 
{ IloExpr expr; RAIIExpr(RAIIExpr const&); RAIIExpr& operator=(RAIIExpr const&); 

public: RAIIExpr(IloEnv env) : expr(env) 
{
} ~RAIIExpr() 
{ expr.end(); 
} template<typename T> RAIIExpr& operator+=(T const& t) 
{ expr += t; 

return *

this; 
} ...

All of this is far from perfect but it helps avoiding common mistakes.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

You must call IloExpr::end of all IloExpr's. Their destructor does not deallocate them.
#DecisionOptimization
#MathematicalProgramming-General