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

Thu Jan 24 17:06:56 MET 2013

Hi Alessa,

please have a look the papers about "Arc-time Indexed Formulations for
Single and Parallel Machine Scheduling Problems" by Pessoa, Uchoa, Poggi
de Aragão, and Rodrigues.

Best,
Gerald

On 15.01.2013 13:38, Alessia Violin wrote:
> 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
>