Adaptive Stabilization Based on Machine Learning for Column Generation
This addresses a bottleneck in large-scale linear programming for optimization practitioners, offering incremental improvements over existing stabilization methods.
The paper tackles the problem of heavy oscillation in dual values during column generation, which slows convergence, by introducing a machine learning approach to predict optimal dual solutions and an adaptive stabilization technique, achieving a significantly improved convergence rate on the graph coloring problem.
Column generation (CG) is a well-established method for solving large-scale linear programs. It involves iteratively optimizing a subproblem containing a subset of columns and using its dual solution to generate new columns with negative reduced costs. This process continues until the dual values converge to the optimal dual solution to the original problem. A natural phenomenon in CG is the heavy oscillation of the dual values during iterations, which can lead to a substantial slowdown in the convergence rate. Stabilization techniques are devised to accelerate the convergence of dual values by using information beyond the state of the current subproblem. However, there remains a significant gap in obtaining more accurate dual values at an earlier stage. To further narrow this gap, this paper introduces a novel approach consisting of 1) a machine learning approach for accurate prediction of optimal dual solutions and 2) an adaptive stabilization technique that effectively capitalizes on accurate predictions. On the graph coloring problem, we show that our method achieves a significantly improved convergence rate compared to traditional methods.