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

Yu Yang ()
Additional contact information
Yu Yang: Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611

Operations Research, 2025, vol. 73, issue 3, 1184-1207

Abstract: 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.

Keywords: Transportation; column generation; variable fixing; Lagrangian underestimate; multitrip vehicle routing (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.0398 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:3:p:1184-1207

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().