<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">Hi Alessia,<br>
<br>
first a short explanation of how the deletion of variables works,
but let us start with the concept of removable columns.<br>
<br>
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.<br>
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.<br>
<br>
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.<br>
<br>
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).<br>
<br>
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.<br>
<br>
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.<br>
<br>
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.<br>
<br>
Best,<br>
Gerald<br>
<br>
On 03.10.2013 17:06, Alessia Violin wrote:<br>
</div>
<blockquote cite="mid:524D87EF.9090303@ulb.ac.be" type="cite">
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
<div class="moz-cite-prefix">Hello again,<br>
<br>
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.<br>
<br>
I continued investigating and I realized I didn't get the
statistics completely correctly, sorry.<br>
If I don't delete variables, I get<br>
total solving time = time for pricing (subproblem) + time for LP
(master) + very small time<br>
Now, deleting variables I get<br>
total solving time = time for pricing + time for LP + a
significant amount of time<br>
<br>
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?).<br>
<br>
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?<br>
And then, if variables are not deleted during the solving, why
do is the LP solving time smaller?<br>
<br>
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.<br>
<br>
Thanks again, this functionality is a bit obscure to me.<br>
<br>
Alessia<br>
<br>
<br>
<br>
<br>
<br>
On 10/01/2013 05:07 PM, Marco Lübbecke wrote:<br>
</div>
<blockquote
cite="mid:CAM5ELAosYQj0i+CdU+=10Y1sPFBrdF61RxaXbednUx9F=NkOHA@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra"><br>
<div class="gmail_quote">2013/10/1 Alessia Violin <span
dir="ltr"><<a moz-do-not-send="true"
href="mailto:aviolin@ulb.ac.be" target="_blank">aviolin@ulb.ac.be</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex"> 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.</blockquote>
</div>
<br>
</div>
<div class="gmail_extra">Hi Alessia,<br>
<br>
</div>
<div class="gmail_extra">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.<br>
<br>
</div>
<div class="gmail_extra">Maybe this helps, even though it does
not explain the effect<br>
Marco<br>
<br>
</div>
<div class="gmail_extra"><br>
</div>
</div>
</blockquote>
<div class="moz-cite-prefix">On 10/01/2013 02:41 PM, Alessia
Violin wrote:<br>
</div>
<blockquote cite="mid:524AC313.8080108@ulb.ac.be" type="cite">
<meta http-equiv="content-type" content="text/html;
charset=ISO-8859-1">
Hello,<br>
<br>
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).<br>
I tried to follow instructions reported in the documentation
<meta http-equiv="content-type" content="text/html;
charset=ISO-8859-1">
<a moz-do-not-send="true"
href="http://scip.zib.de/doc/html/FAQ.shtml#Q5.11">http://scip.zib.de/doc/html/FAQ.shtml#Q5.11</a>,
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.<br>
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.<br>
<br>
Do you have any insight of this behavior or any suggestion I
could try?<br>
<br>
I would also like to know how the "deletevars" work, meaning
which is the criteria used to delete a variable?<br>
<br>
Thanks in advance,<br>
<br>
Alessia<br>
<br>
<br>
<pre class="moz-signature" cols="72">--
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: <a moz-do-not-send="true" class="moz-txt-link-abbreviated" href="mailto:aviolin@ulb.ac.be">aviolin@ulb.ac.be</a>
Webpage: <a moz-do-not-send="true" class="moz-txt-link-freetext" href="http://homepages.ulb.ac.be/%7Eaviolin/">http://homepages.ulb.ac.be/~aviolin/</a></pre>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Scip mailing list
<a moz-do-not-send="true" class="moz-txt-link-abbreviated" href="mailto:Scip@zib.de">Scip@zib.de</a>
<a moz-do-not-send="true" class="moz-txt-link-freetext" href="http://listserv.zib.de/mailman/listinfo/scip">http://listserv.zib.de/mailman/listinfo/scip</a>
</pre>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
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: <a moz-do-not-send="true" class="moz-txt-link-abbreviated" href="mailto:aviolin@ulb.ac.be">aviolin@ulb.ac.be</a>
Webpage: <a moz-do-not-send="true" class="moz-txt-link-freetext" href="http://homepages.ulb.ac.be/%7Eaviolin/">http://homepages.ulb.ac.be/~aviolin/</a></pre>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Scip mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Scip@zib.de">Scip@zib.de</a>
<a class="moz-txt-link-freetext" href="http://listserv.zib.de/mailman/listinfo/scip">http://listserv.zib.de/mailman/listinfo/scip</a>
</pre>
</blockquote>
<br>
</body>
</html>