An official website of the United States government
For vehicle routing problems, strong dual bounds on the optimal value are needed to develop scalable exact algorithms as well as to evaluate the performance of heuristics. In this work, we propose an iterative algorithm to compute dual bounds motivated by connections between decision diagrams and dynamic programming models used for pricing in branch-and-cut-and-price algorithms. We apply techniques from the decision diagram literature to generate and strengthen novel route relaxations for obtaining dual bounds without using column generation. Our approach is generic and can be applied to various vehicle routing problems in which corresponding dynamic programming models are available. We apply our framework to the traveling salesman with drone problem and show that it produces dual bounds competitive to those from the state of the art. Applied to larger problem instances in which the state-of-the-art approach does not scale, our method outperforms other bounding techniques from the literature. Funding: This work was supported by the National Science Foundation [Grant 1918102] and the Office of Naval Research [Grants N00014-18-1-2129 and N00014-21-1-2240]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2021.0170 .
more »
« less
This content will become publicly available on May 1, 2026
DeLuxing: Deep Lagrangian Underestimate Fixing for Column-Generation-Based Exact Methods
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.
more »
« less
- Award ID(s):
- 2309667
- PAR ID:
- 10596756
- Publisher / Repository:
- INFORMS
- Date Published:
- Journal Name:
- Operations Research
- Volume:
- 73
- Issue:
- 3
- ISSN:
- 0030-364X
- Page Range / eLocation ID:
- 1184 to 1207
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Routing a Vehicle to Collect Data After an Earthquake In the immediate aftermath of a major earthquake, it is crucial to quickly and accurately assess structural damage throughout the region. It is especially important to identify buildings that have become unsafe in order to prioritize evacuation efforts. Only a very small number of building inspections can be feasibly performed in a narrow time frame; however, their results can then be combined with other data sources to predict damage at other locations that were not inspected. In “D-Optimal Orienteering for Postearthquake Reconnaissance Planning,” Wang, Xie, Ryzhov, Marković, and Ou present a novel nonlinear integer program that combines vehicle routing with a statistical objective, the goal being to maximize data quality. An exact method based on row and column generation is developed to solve problems with up to 200 buildings. The approach is validated in a realistic case study using real-world building data obtained from a state-of-the-art earthquake simulator.more » « less
-
We consider a variant of the vehicle routing problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation-based linear-programming relaxation for this VRP. Specifically, we focus on algorithms for the “pricing problem,” which corresponds to the resource-constrained elementary shortest path problem. The first algorithm extends the pulse algorithm for which we derive a new bounding scheme on the maximum load of any route. The second algorithm is based on random coloring from parameterized complexity which can be also combined with other techniques in the literature for improving VRPs, including cutting planes and column enumeration. We conduct numerical studies using VRP benchmarks (with 50–957 nodes) and instances of a medical home care delivery problem using census data in Wayne County, Michigan. Using parallel computing, both pulse and random coloring can significantly improve column generation for solving the linear programming relaxations and we can obtain heuristic integer solutions with small optimality gaps. Combining random coloring with column enumeration, we can obtain improved integer solutions having less than 2% optimality gaps for most VRP benchmark instances and less than 1% optimality gaps for the medical home care delivery instances, both under a 30-minute computational time limit. The use of cutting planes (e.g., robust cuts) can further reduce optimality gaps on some hard instances, without much increase in the run time. Summary of Contribution: The vehicle routing problem (VRP) is a fundamental combinatorial problem, and its variants have been studied extensively in the literature of operations research and computer science. In this paper, we consider general-purpose algorithms for solving VRPs, including the column-generation approach for the linear programming relaxations of the integer programs of VRPs and the column-enumeration approach for seeking improved integer solutions. We revise the pulse algorithm and also propose a random-coloring algorithm that can be used for solving the elementary shortest path problem that formulates the pricing problem in the column-generation approach. We show that the parallel implementation of both algorithms can significantly improve the performance of column generation and the random coloring algorithm can improve the solution time and quality of the VRP integer solutions produced by the column-enumeration approach. We focus on algorithmic design for VRPs and conduct extensive computational tests to demonstrate the performance of various approaches.more » « less
-
Abstract This study develops an integrated delivery assignment and route planning strategy for food banking operations, considering food supply and demand constraints, food item restrictions, and vehicle capacity constraints. A mixed‐integer linear model is formulated to maximize the total demand served and minimize the total travel cost imposed on delivery volunteers. An integrated solution algorithm is developed that includes Lagrangian relaxation and column generation. The algorithm decomposes the problem into assignment and routing components and solves each iteratively. The proposed methodology is applied to a case study in Wake County, NC. A series of sensitivity analyses are conducted to draw insights. The numerical results demonstrate the proposed methodology's capacity to solve complex problems in food delivery operations efficiently.more » « less
-
Li, Yingzhen; Mandt, Stephan; Agrawal, Shipra; Khan, Emtiyaz (Ed.)Optimization problems with norm-bounding constraints appear in various applications, from portfolio optimization to machine learning, feature selection, and beyond. A widely used variant of these problems relaxes the norm-bounding constraint through Lagrangian relaxation and moves it to the objective function as a form of penalty or regularization term. A challenging class of these models uses the zero-norm function to induce sparsity in statistical parameter estimation models. Most existing exact solution methods for these problems use additional binary variables together with artificial bounds on variables to formulate them as a mixed-integer program in a higher dimension, which is then solved by off-the-shelf solvers. Other exact methods utilize specific structural properties of the objective function to solve certain variants of these problems, making them non-generalizable to other problems with different structures. An alternative approach employs nonconvex penalties with desirable statistical properties, which are solved using heuristic or local methods due to the structural complexity of those terms. In this paper, we develop a novel graph-based method to globally solve optimization problems that contain a generalization of norm-bounding constraints. This includes standard ℓp-norms for p∈[0,∞) as well as nonconvex penalty terms, such as SCAD and MCP, as special cases. Our method uses decision diagrams to build strong convex relaxations for these constraints in the original space of variables without the need to introduce additional auxiliary variables or impose artificial variable bounds. We show that the resulting convexification method, when incorporated into a spatial branch-and-cut framework, converges to the global optimal value of the problem. To demonstrate the capabilities of the proposed framework, we conduct preliminary computational experiments on benchmark sparse linear regression problems with challenging nonconvex penalty terms that cannot be modeled or solved by existing global solvers.more » « less
