[Scip] cleanupcols at selective nodes

[Gerald Gamrath]

Hi Sebastian,

it is mainly a data structure issue. The basis information is stored at
each node as a bit array, in the order in which the columns are
contained in the LP. When a variable is contained in the LP after a node
is processed and thus information about it is stored in the basis
information array of that node, it will always stay in the LP. Thus,
whenever a basis is loaded, the information always corresponds to the
first variables in the LP, while there is no information for those which
were added to the LP in the meantime, which are also the last ones.

Therefore, if you would like to remove a column from the LP later, you
would need to go through all the bit arrays storing the basis
information and remove the entry for this one variable, shifting all
other entries to the left. This would be a lot of work and is currently
not supported.

What you could try is keeping lp/cleanupcols set to FALSE, to not remove
all variables, but decrease the age limit for columns in order to remove
more columns from the LP at each node. This can be done via the
parameter lp/colagelimit, which is per default set to 10 and defines the
number of times a variable needs to be nonbasic in successive LP
solutions before it is removed from the LP.

Best,
Gerald

Am 07.12.2012 10:06, schrieb Sebastian Ruther:
>   Hello again,
>
> I have a question about cleaning up columns at nodes. In a nutshell:
> I'm wondering why, when getting to a node, I'm not allowed to remove all 
> columns from the LP that are not part of the basis of the parent node. I 
> understand that physically deleting them is a bad idea but removing 
> them, i.e. transferring them to the varpricer, shouldn't be a problem?
>
>
>
> What I ultimately want to do is:
> My master problem is hard to solve. I can set lp/cleanupcols to TRUE, 
> which keeps the MP small. However, this results in calling varpricer 
> (and thus solving an LP) sometimes several hundred times before I get to 
> add variables in my own pricer. This takes too long.
> The other extreme is to use lp/cleanupcols = FALSE, which means 
> varpricer is called less often but every lp solve call takes several 
> seconds, which in the end also takes too long as well.
> So I would like to balance this and only remove columns from the lp once 
> a certain threshold on the number of variables is exceeded. The problem 
> is that it then only removes the columns it added at the current node, 
> which does not result in a sufficient reduction. In focusnodeToFork i 
> would like to call SCIPlpCleanupAll instead of SCIPlpCleanupNew but I 
> don't seem to be allowed to do so. It asserts when I do that.
>
> Here is what I understand (think I understand):
> I set lp/cleanupcols to TRUE and printed the number of columns every 
> time CPLEX is called. What I see is that when solveNodeInitialLP is 
> called for two siblings (say node 4 and 5), the LP starts with the same 
> number of columns. So the information which columns are in the LP must 
> be coming from the parent (here node 2).  Lets say node 4 is executed 
> first, some others follow, and then node 5 is selected. In that case the 
> lpi holds an LP that may have all sorts of variables. In this setting, 
> SCIP goes through the variables and removes all but the ones that the 
> parent marked as necessary.
> So technically it does exactly what I think would be necessary for my 
> strategy: removes all unimportant columns and adds those that the basis 
> requires ( SCIPtreeLoadLP can "add the missing columns and rows").
>
> To come back to my question: Why can't I call SCIPlpCleanupAll instead 
> of SCIPlpCleanupNew?
>
> Regards,
> Sebastian
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip