[Scip] deleting variables in column generation

Fri Oct 4 16:13:49 CEST 2013

Hi Alessia,

first a short explanation of how the deletion of variables works, but
let us start with the concept of removable columns.

SCIP implements an aging of columns and columns are removed from the LP
whenever their age is above some threshold. Whenever a variable has
value 0.0 in an LP solution, its age is increased by 1, if it has a
different value, the age is reset to 0. After each LP solve, all
nonbasic columns are removed when their age exceeds the limit (which is
10 by default), additionally, whenever the processing of a node is
finished, all non-basic variables with a value of 0.0 can be removed.
In order to enable the aging, you need to make your variables removable;
if you want to have the cleanup at the end of each node (the root), you
need to set lp/cleanupcols(root) to TRUE.

This will remove the columns from the LP, but the corresponding
variables still exist in your problem. Thus, there is a special pricer
within SCIP called variable pricer which checks these variables for
negative reduced costs and adds them to the LP again, if needed.

An important think to mention at this point is that SCIP only allows to
remove columns from the LP at the same node where they were created,
before the node was completely processed. After that, the variable is
will be part of the basis information stored at that node. This basis
information is stored in a compressed form which relies on the fact that
from a node to its child, only new columns can be added, but none
removed. Deleting the variable later would mean that SCIP must to go
through all the basis information stored at nodes within the tree and
remove the information about that column, which would be too expensive.
Since after the root, you only get an output line at the end of each
node, this explains why the number of variables does not decrease during
solving (it should decrease once at the root, however).

If you mark the variables to be deletable and set
"pricing/delvars(root)" to TRUE, also the variables themselves will be
deleted from your problem. This should mainly be used if you run out of
memory because you create too many variables. If you enable this, after
the processing of a node, all variables created at that node are checked
and in case their column is currently not part of the LP, the variables
is marked for deletion (of course, variables with a nonzero value in a
solution cannot be deleted, as well as variables which occur in some
other internal structures). After that, the DELVARS callback of all
constraint handlers is called, so that they can remove this variable
from their internal structures (constraints). Please have a look at
cons_setppc.c, where you can see how this is performed and how an event
handler is used before to store which constraints contain deleted variables.

An important thing when deleting variables it to implement this callback
within a constraint handler and capture all variables contained in the
constraints. If you don't do that, SCIP might just remove the variables,
so that the variable pointers in your constraints point to some
arbitrary point in your memory, which might be the reason for your
segmentation fault. SCIPvarIsDeleted() does not help here, because the
variable was already deleted.

As for the different solving time, please send me the statistics printed
at the end of the solving to check where the time might be going. If you
just want to remove your LP solving times and do not have memory
problems, I would suggest to just mark the variables to be removable,
but not deletable.

Best,
Gerald

On 03.10.2013 17:06, Alessia Violin wrote:
> Hello again,
>
> thanks Marco for your hints, once I manage to get this working I will
> try to see what's the best number of variables to keep.
>
> I continued investigating and I realized I didn't get the statistics
> completely correctly, sorry.
> If I don't delete variables, I get
> total solving time = time for pricing (subproblem) + time for LP
> (master) + very small time
> Now, deleting variables I get
> total solving time = time for pricing + time for LP + a significant
> amount of time
>
> When deleting variables the total solving time is bigger and the time
> for the pricing is constant, so I was assuming the time for LP to be
> bigger, but actually the time for LP is smaller. The increase of time
> seems spent at the end of the solving (when the gap is zero) and
> before the solution and statistics are printed. I don't know what scip
> is doing at this point (maybe deleting variables here?).
>
> The number of variables during the solving always increases, meaning
> that nothing is deleted during the solving? The number of variables at
> the very end, after the solving is finished, is smaller, so variables
> are deleted at the end of the LP solving?
> And then, if variables are not deleted during the solving, why do is
> the LP solving time smaller?
>
> I also tried to include this "delvars" functionality to solve the
> integer problem, so in the tree. My model includes a Constraint
> Handler to perform the branching, and I get a segmentation fault in
> the scip_enfolp and scip_check callbacks, in particular when using the
> function SCIPgetSolVal. I tried to add an if (not(SCIPvarIsDeleted)),
> to avoid accessing deleted variables, but it is not working, and I
> don't know what else to try.
>
> Thanks again, this functionality is a bit obscure to me.
>
> Alessia
>
>
>
>
>
> On 10/01/2013 05:07 PM, Marco Lübbecke wrote:
>>
>> 2013/10/1 Alessia Violin <aviolin at ulb.ac.be <mailto:aviolin at ulb.ac.be>>
>>
>>     So, I was wondering from where this increase comes from. In
>>     theory as I delete columns the Master is smaller, so it should be
>>     quicker to solve.
>>
>>
>> Hi Alessia,
>>
>> this "smaller = faster" is true if "smaller" means less rows. In
>> column generation it is my experience (however, I tried to delete
>> vars last time some 12 years ago...) that it is detrimental to
>> performance if you delete TOO MANY variables (like: all except the
>> current basis). The "Montreal gangsters" (J.Desrosiers etc.) claim
>> that they keep about 2-3 times the number of rows. The selection of
>> which to keep is according to age and reduced cost.
>>
>> Maybe this helps, even though it does not explain the effect
>> Marco
>>
>>
> On 10/01/2013 02:41 PM, Alessia Violin wrote:
>> Hello,
>>
>> I am solving the linear relaxation of a problem with column
>> generation, and I wanted to try deleting columns in the solving
>> process, to reduce the size of the Master Problem and its solving
>> time (which seems to be the bottleneck for my problem).
>> I tried to follow instructions reported in the documentation
>> http://scip.zib.de/doc/html/FAQ.shtml#Q5.11, using the parameters
>> "pricing/delvars and delvarsroot". I marked my variables as deletable
>> as well. Everything works, and as results I get less columns at the
>> end (which is normal), and in the process I generate the same number
>> of columns as without the delete, meaning (I think) that only useless
>> columns are deleted, which is also nice. The weird part is that the
>> solving time of the version with the delete is bigger, and this
>> increase is for solving the Master Problem (the time for the pricer
>> stays the same). So, I was wondering from where this increase comes
>> from. In theory as I delete columns the Master is smaller, so it
>> should be quicker to solve.
>> Then I also tried to play with parameters "lp/colagelimit" and
>> "lp/cleanupcols and cleanupcolsroot", but changing their values does
>> not affect at all the solution time, the number of columns at the end
>> or the number of columns generated in the solving.
>>
>> Do you have any insight of this behavior or any suggestion I could try?
>>
>> I would also like to know how the "deletevars" work, meaning which is
>> the criteria used to delete a variable?
>>
>> Thanks in advance,
>>
>> Alessia
>>
>>
>> -- 
>> Alessia Violin
>> Service Graphes et Optimisation Mathématique (G.O.M.)
>> Université Libre de Bruxelles
>> C.P. 210/01
>> Boulevard du Triomphe
>> B-1050 BRUXELLES
>> Tel: 02 650 58 80 - Fax: 02 650 59 70
>> Email: aviolin at ulb.ac.be
>> Webpage: http://homepages.ulb.ac.be/~aviolin/
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>
> -- 
> Alessia Violin
> Service Graphes et Optimisation Mathématique (G.O.M.)
> Université Libre de Bruxelles
> C.P. 210/01
> Boulevard du Triomphe
> B-1050 BRUXELLES
> Tel: 02 650 58 80 - Fax: 02 650 59 70
> Email: aviolin at ulb.ac.be
> Webpage: http://homepages.ulb.ac.be/~aviolin/
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20131004/2d9c196d/attachment.html>