[Scip] deleting variables in column generation

[Alessia Violin]

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/

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20131003/625fdaed/attachment.html>