[Scip] update of upper bound and coefficient of variables during pricing in column generation

Gerald Gamrath gamrath at zib.de
Tue Jan 15 12:33:18 MET 2013


Hi Alessa, hi Tue,

unfortunately, it is not allowed to relax the bounds of a variable or
change its objective during the solving process. The reason is what Tue
already explained: A lot of decisions are taken using this information,
e.g. reducing variables' domains by presolving and domain propagation or
bounding branch-and-bound nodes. Changing bounds or objective
coefficients after this was done might invalidate these decisions.

In your special case, you just want to change slack variables used for
stabilization issues only. So you could argue that this does not
influence these decisions. I do not know how exactly you want to do the
stabilization, but I'm pretty sure that just allowing to change these
variables would not be sufficient. To guarantee that the slack variables
do not influence the search, you have to make sure that they have value
0 at the end of the pricing loop, right? Otherwise, they change the
lower bound computed by the LP. Therefore, the current behaviour of SCIP
would have to be changed, which continues pricing if and only if a new
variable was added to the LP. In the stabilization case, even if no
variable was added, you might need to adjust the stabilization box, thus
change the LP, solve it again and perform pricing with the changed dual
solution.

I see that stabilization is an important feature but as I tried to
explain, it needs quite a lot of changes in the main solving loop of
SCIP and we did not manage to do it yet, but it is on our list for
future releases. Until then, you could try using a dual variable
smoothing approach for the stabilization, which does not need slack
variable and can thus easily be implemented in SCIP.

Best,
Gerald

Am 15.01.2013 10:03, schrieb Tue Christensen:
> Sorry, I was too fast. The function SCIPchgVarObj does not allow you to change the objective function coefficient beyond the scip_stage_presolving. The reason for this might be what I explained below (it could invalidate presolving => fixing of variables). 
>
> I will leave this question to the experts!
>
> Cheers,
>
> Tue
>
> -----Original Message-----
> From: scip-bounces at zib.de [mailto:scip-bounces at zib.de] On Behalf Of Tue Christensen
> Sent: 15. januar 2013 08:55
> To: Alessia Violin; scip at zib.de
> Subject: Re: [Scip] update of upper bound and coefficient of variables during pricing in column generation
>
> Hello Alessia!
>
> For changing the upper bound of a variable I have used:
>
> SCIPchgVarUb(SCIP * 	scip, SCIP_VAR * var, SCIP_Real 	newbound) 
>
> See http://scip.zib.de/doc/html_devel/scip_8c.shtml#a467948c18929421bcc14c1c009f58c56
>
> *I think* you can run into troubles if you try to add a higher bound than the one currently present (since solutions that was infeasible could now become feasible and possibly invalidate your branching tree and/or presolving). 
>
> For changing the objective function coefficient you can use:
>
> SCIPchgVarObj(SCIP * 	scip,SCIP_VAR * var,SCIP_Real newobj)	
>
> See http://scip.zib.de/doc/html_devel/scip_8c.shtml#ac8033a7019d8bd6f9e6889cd2edc4463 
>
> In case of troubles you can just skype me!
>
> Cheers,
>
> Tue Christensen
>
> -----Original Message-----
> From: scip-bounces at zib.de [mailto:scip-bounces at zib.de] On Behalf Of Alessia Violin
> Sent: 14. januar 2013 15:50
> To: scip at zib.de
> Subject: [Scip] update of upper bound and coefficient of variables during pricing in column generation
>
> Hello,
>
> I have implemented a column generation procedure in SCIP (using c++) and now I am trying to use a stabilization procedure to improve it. I am doing this by adding some slack variables in the master problem, and I would like to change the upper bound of these variables during the pricing. Is there a method that allows me to do this?
> Furthermore I also would like to change the coefficient of those variables in the objective function, during the pricing.
> I have done my best to look through the documentation, but I was not able to find how to do these updates.
>
> If there are no methods, could anyone give me a suggestion on the simplest way to do it?
>
> Many thanks in advance for any help!
>
> Alessia Violin
>
> --
> 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
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip



More information about the Scip mailing list