Graph Reduction with Unsupervised Learning in Column Generation: A Routing Application

Column Generation (CG) is a popular method dedicated to enhancing computational efficiency in large scale Combinatorial Optimization (CO) problems. It reduces the number of decision variables in a problem by solving a pricing problem. For many CO problems, the pricing problem is an Elementary Shortest Path Problem with Resource Constraints (ESPPRC). Large ESPPRC instances are difficult to solve to near-optimality. Consequently, we use a Graph neural Network (GNN) to reduces the size of the ESPPRC such that it becomes computationally tractable with standard solving techniques. Our GNN is trained by Unsupervised Learning and outputs a distribution for the arcs to be retained in the reduced PP. The reduced PP is solved by a local search that finds columns with large reduced costs and speeds up convergence. We apply our method on a set of Capacitated Vehicle Routing Problems with Time Windows and show significant improvements in convergence compared to simple reduction techniques from the literature. For a fixed computational budget, we improve the objective values by over 9% for larger instances. We also analyze the performance of our CG algorithm and test the generalization of our method to different classes of instances than the training data. Introduction Real-life decision-making problems can often be modeled by Combinatorial Optimization (CO). Practical problem instances, however, usually have much larger sizes than instances often encountered in the literature (Luo et al., 2024), while requiring good solutions in limited time. This invokes the need for specialized methods capable of scaling to the large instances of these problems. Column Generation (CG) is often regarded as an efficient technique to address many CO problems such as Vehicle Routing and Crew Scheduling (Desaulniers et al., 2006), as it keeps the number To identify variables which contribute to the objective value of a problem, i.e. with non-zero reduced cost, a Pricing Problem (PP) has to be solved. As during the CG algorithm, many Pricing Problems have to be considered, the efficiency of the method lies in the ability to solve the PP efficiently(Václavík et al., 2018).