Accelerating the stabilized column generation using machine learning

Abstract

Column Generation (CG) is a well-established methodology for tackling large-scale real-world optimization problems. Nevertheless, as problem sizes increase, challenges like long-tail effects and degeneracy become more prevalent. Various strategies for stabilizing dual variables have demonstrated their effectiveness in mitigating these challenges. Generally, numerical tests are employed to identify the best parameter values for stabilized CG using different configurations for the same problem. This study introduces an innovative approach using machine learning (ML) to predict the best algorithm configuration, eliminating the need for extensive numerical experimentation. The core objective of this study is to predict optimal dual variables to generate improved bounds in the Restricted Master Problem of stabilized CG. By and large, this comprehensive approach represents a robust and flexible framework, optimizing algorithm configurations and expediting the convergence of the CG model. Extensive computational experiments confirm the efficacy of our ML-based approach in accurately predicting optimal dual variables and outperforming conventional methods. The practical utility is exemplified in optimizing workforce scheduling, demonstrating significant reductions in computational time across problem instances. This real-world application highlights the remarkable benefits of the smart approach in enhancing the efficiency and effectiveness of CG-based optimization solution.