[Scip] tail effect

[marco.luebbecke@googlemail.com]

Hi Mattia,

When you stabilize like in the Frangioni paper you add these "soft box constraints" to the duals which means that you add variables in the master, the procedure is described in that paper, you do not need to compute any duals yourself, the additional primal variable do this automatically, which is an advantage over computing stabilized duals yourself like in a recent suggestion by Uchoa et al. (a maschine scheduling preprint, I forgot the title). Yesterday we implemented the latter, more static approach, and it did not work too well, so (a) do what Frangioni says, (b) or use an interior point method to solve the master, (c) or use the bundle method, (d) or have a look at an encyclopedia article I finished a few days ago, topmost on my pubs page.

Have fun
Marco



-- not in my office...
Mattia Barbieri <barbieri.mattia at gmail.com> schrieb am 11.06.2010 17:06: 

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/b62cb4c4/attachment.html