Machine Learning–Enhanced Column Generation for Large-Scale Capacity Planning Problems

Capacity Planning problems are a class of optimization problems used in diverse industries to improve resource allocation and make investment decisions. Solving real-world instances of these problems typically requires significant computational effort. To tackle this, we propose machine-learning-aided column generation methods for solving large-scale capacity planning problems. Our goal is to accelerate column generation by approximating the pricing subproblems while preserving the ability to certify solution quality. We investigate two strategies embedded within the column generation framework: (i) a surrogate-based pricing approach that replaces the operational component of the pricing problem with a pre-trained multi-layer neural network with ReLU activations, incorporated through a mixed-integer linear (MILP) encoding of the network; and (ii) end-to-end approaches that learn to directly propose new columns. To retain performance guarantees, we adopt a two-phase procedure: an initial surrogate phase rapidly generates valid columns and approximate bounds, followed by a standard column generation phase that solves the original pricing subproblems to recover valid bounds and compute the optimality gap. Computational results show that the intermediate surrogate phase is beneficial in practice: it yields substantial runtime improvements, and the columns produced during the approximate phase are of sufficient quality to significantly speed up convergence in the subsequent exact phase.

Article

Download

View PDF