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

[Alessia Violin]

Hello,

thanks a lot for your answer and explanation.

My stabilization was intended as you explained, having slack variables 
equal to zero at the end of the pricing, penalizing them if positive 
through the resolution. As I was still searching for how to modify 
bounds and objectives, I didn't go through how to continue the pricing 
even if there are no new variables, which in effect would have been also 
a problem.

I will have a look to the other stabilization approach you suggested, 
thanks. Do you have any reference on this?

best,

Alessia



On 01/15/2013 12:33 PM, Gerald Gamrath wrote:
> 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

-- 
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/