11
$\begingroup$

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)1)


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.

$\endgroup$
11
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – German Velasquez Diaz Oct 9 '19 at 20:48
  • $\begingroup$ Yes, they can be run in parallel $\endgroup$ – Ruslan Sadykov Oct 10 '19 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.