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.
