DeLuxing: Deep Lagrangian Underestimate Fixing for Column-Generation-Based Exact Methods
提出DeLuxing变量固定方法，通过拉格朗日下界消除超过75%的不必要变量，使可最优求解的带时间窗多程车辆路径问题规模翻倍，并加速顶级求解器RouteOpt达71%。
Advancing Column Generation by a Novel Variable Fixing Method In the paper titled “DeLuxing: Deep Lagrangian Underestimate Fixing for Column-Generation-Based Exact Methods,” Dr. Yu Yang introduces DeLuxing—an innovative variable-fixing technique that significantly advances column-generation-based exact methods for solving large-scale optimization problems, particularly vehicle routing problems (VRPs). DeLuxing leverages a novel linear programming formulation with a small subset of the enumerated variables, which is theoretically guaranteed to yield qualified dual solutions for computing Lagrangian underestimates. By eliminating over 75% of the unnecessary variables, DeLuxing drastically boosts computational efficiency, doubling the size of CMTVRPTW (capacitated multitrip vehicle routing problem with time windows) instances that can be solved optimally. Additionally, this breakthrough accelerates top VRP solvers like RouteOpt by up to 71%. The core concept underpinning DeLuxing extends to broader contexts such as variable type relaxation and cutting plane addition, achieving an additional 25% speedup for difficult instances.