Minimum norm dual solutions and column generalisation stabilisation

Abstract

Column generation is an important technique for solving very large-scale integer programming problems, with important applications in crew scheduling and vehicle routing. However, it has been observed that the column generation updates can be "unstable", in that dual prices vary excessively between iterations, and the algorithm produces many unnecessary columns. One possible explanation for this behaviour is that the dual problem is massively degenerate. We consider using the optimal dual vector with minimum norm, and show that on binary cutting stock problems, this can reduce the number of iterations required. It does not explain, however, all of the improvement shown by recent column generation stabilization techniques.