[Scip] tail effect

[Mattia Barbieri]

Hi all,
 developing my Branch&Price application (an application similar to
Multi-Depot Vehicle Scheduling Problem), I found that the slow convergence
may be due to the tail effect. I know that there are some approaches to work
around this problem, for example, defining a stability center int the dual
objective function that penalizes moves far from it (this should reducing
the number and the magnitude of oscillations of dual variables during Column
Generation process). Thus I have to change the dual objective function in
such a way to consider the stability center, more precisely, max{u_i + D(u_i
- c)} where terms u_i are the dual variables relative to the Master LP, and
c is the current stability center (to be updated). D is the stabilizing
function, meant to avoid large fluctuations of u_i by penalizing point "too
far" from the current stability center c. (D will be futhermore defined as a
5-piecewise linear penalty function). [See B.Amor, J. Desrosiers, A.
Frangioni - Stabilization in Column Generation]
 Whitouth going inside my implementation strategies, how can I add such
duals information? I would like to have new dual variable values before the
pricing routine starts its search for new negative reduced costs variables.
 Or do you have any other ideas/approaches to solve the tail effect?

 Thanks in advance.
 Best regards.

-- 
Mattia Barbieri
barbieri.mattia at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20100611/8457e208/attachment.html