DeLuxing: Deep Lagrangian Underestimate Fixing for Column-Generation-Based Exact Methods

In this paper, we propose an innovative variable fixing strategy called de ep L agrangian u nderestimate fi xing (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). Because of 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 multitrip vehicle routing problem with time windows (CMTVRPTW), its two important variants with loading times or release dates, and the classic capacitated VRP (CVRP) and VRPTW. Enhanced by DeLuxing and the extensions, one of the best exact methods for solving the CMTVRPTW 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, by 45% and 71%, respectively, for solving the 200-node CVRP and 300-node VRPTW instances. Although DeLuxing is less effective for longer routes, it still contributes to an effective primal heuristic.