[hal-01077984] Automation and combination of linear-programming based stabilization techniques in column generation

The convergence of a column generation algorithm can be improved in practice by using so-called stabilization techniques Proximal methods based on penalising the deviation from the incumbent dual solution have become standards of the domain However the analysis of such methods is important to understand the mechanism on which they rely to appreciate the difference between methods and to derive intelligent schemes to adjust their parameters As stabilization procedures for column generation can be viewed as cutting plane strategies in the dual problem the link with cutting plane separation strategies can be exploited to enlarge the scope of methods and to refine their analysis Here we focus on stabilization schemes that rely solely on a linear programming LP solver for the column generation master program This restrictive scope captures the most common implementations where one uses an LP solver to handle the master program For dual price smoothing techniques we analyse the link with the in-out separation strategy and we derive generic convergence properties For penalty function methods as well as for smoothing we describe proposals for parameter self-adjusting schemes Such schemes make initial parameter tuning less of an issue as corrections are made Also the dynamic adjustments compared to a static setting allows to adapt the parameters to the phase of the algorithm We provide extensive test reports that highlight the comparative performances of such scheme and validate our self-adjusting parameter scheme Furthermore our results show that using smoothing in combination with penalty function yields a cumulative effect on convergence speed-ups



from HAL : Dernières publications http://ift.tt/12YLAWB