In this paper, we propose an innovative variable fixing strategy called deep Lagrangian underestimate fixing (DeLuxing). It is a highly effective approach for removing unnecessary variables in column-generation (CG)-based exact methods used to solve challenging discrete optimization problems commonly encountered in various industries, including vehicle routing problems (VRPs). DeLuxing employs a novel linear programming (LP) formulation with only a small subset of the enumerated variables, which is theoretically guaranteed to yield qualified dual solutions for computing Lagrangian underestimates (LUs). Due to their small sizes, DeLuxing can efficiently solve a sequence of similar LPs to generate multiple high-quality LUs, and thus can, in most cases, remove over 75% of the variables from the enumerated pool. We extend the fundamental concept underpinning the new formulation to contexts beyond variable fixing, namely variable type relaxation and cutting plane addition. We demonstrate the effectiveness of the proposed method in accelerating CG-based exact methods via the capacitated multi-trip vehicle routing problem with time windows (CMTVRPTW), its two important variants with loading times or release dates, and the classic CVRP and VRPTW. Enhanced by DeLuxing and the extensions, one of the best exact methods for solving the CMTVRPTW developed in Yang (2023) doubles the size of instances solved optimally for the first time while being more than 7 times on average and up to over 20 times as fast as top-performing exact methods reported in the literature. It further accelerates RouteOpt, one of the world’s fastest VRP solvers (You et al. 2023), by 45% and 71%, respectively, for solving the 200-node CVRP and 300-node VRPTW instances. While DeLuxing is less effective for longer routes, it still contributes to an effective primal heuristic.
Article
View DeLuxing: Deep Lagrangian Underestimate Fixing for Column-Generation-Based Exact Methods