Stabilization techniques in column generation when subproblems are not solved optimally

Question

Which stabilization techniques in column generation, like penalty function approaches and dual price smoothing, can be used when subproblems are not solved optimally? (I am particularly interested in the parameter-less dual price smoothing approach proposed by Pessoa et al. (2013)¹)

_Reference

_{[1] Pessoa, A., Sadykov, R., Uchoa, E., Vanderbeck, F. (2013). In-Out Separation and Column Generation Stabilization by Dual Price Smoothing. Lecture Notes in Computer Science Volume 7933, 12th International Symposium on Experimental Algorithms, Rome, Italy. DOI: 10.1007/978-3-642-38527-8_31.}

score 12 · Accepted Answer · answered Oct 09 '19 at 07:33

I am a co-author of this paper. The parameter-less dual price smoothing approach can totally be used even if pricing subproblems are solved heuristically. We do it very often. When calculating the sub-gradient, you just use your best heuristic solutions (in terms of reduced cost) for the pricing subproblems. Of course, the better is your heuristic, the better will be the stabilization effect.

The only condition to use this technique is that you need to solve (exactly or heuristically) all your pricing subproblems in every column generation iteration, in order to calculate the sub-gradient. This may be slow if there are many subproblems.

P.S. The full version of the paper is published here: http://dx.doi.org/10.1287/ijoc.2017.0784

Thanks for the clarification. In the case where there are many subproblems, they can still be run in parallel and save some runtime. Is this correct? — German Velasquez Diaz, Oct 09 '19 at 20:48

Stabilization techniques in column generation when subproblems are not solved optimally

1 Answers1