Column Elimination for Capacitated Vehicle Routing Problems

We introduce a column elimination procedure for the capacitated vehicle routing problem. Our procedure maintains a decision diagram to represent a relaxation of the set of feasible routes, over which we define a constrained network flow. The optimal solution corresponds to a collection of paths in the decision diagram and yields a dual bound. The … Read more

Efficient Discovery of Cost-effective Policies in Sequential, Medical Decision-Making Problems

Cost-effectiveness analysis is widely used by policymakers to prioritize interventions that improve a population’s health. Net monetary benefit (NMB) is a metric used for the comparison of medical care strategies, which converts an intervention’s health-benefits to monetary value using the willingness to pay (WTP) as the exchange rate. There is no universally accepted value for … Read more

The min-Knapsack Problem with Compactness Constraints and Applications in Statistics

In the min-Knapsack problem, one is given a set of items, each having a certain cost and weight. The objective is to select a subset with minimum cost, such that the sum of the weights is not smaller than a given constant. In this paper we introduce an extension of the min-Knapsack problem with additional … Read more

Transportation and Inventory Planning in Serial Supply Chain with Heterogeneous Capacitated Vehicles

We study serial supply chain problems where a product is transported from a supplier to a warehouse (inbound transportation), and then from the warehouse (outbound transportation) to a retailer such that demand for a given planning horizon is satisfied. We consider heterogeneous vehicles of varying capacities for the transportation in each time period, and the … Read more

Decremental State-Space Relaxations for the Basic Traveling Salesman Problem with a Drone

Truck-and-drone routing problems have become an important topic of research in the last decade due to their applications for last-mile deliveries. Despite the large number of publications in this area, the most efficient exact algorithms designed thus far struggle to solve the benchmark instances with 39 or more customers. This fact is true even for … Read more

Data-driven Multistage Distributionally Robust Optimization with Nested Distance: Time Consistency and Tractable Dynamic Reformulations

We study multistage distributionally robust optimization in which the uncertainty set consists of stochastic processes that are close to a scenario tree in the nested distance (Pflug and Pichler (2012)). Compared to other choices such as Wasserstein distance between stochastic processes, the nested distance accounts for information evolution, making it hedge against a plausible family … Read more

A Fast Combinatorial Algorithm for the Bilevel Knapsack Problem with Interdiction Constraints

\(\) We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and \(n\) items. The objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of … Read more

Compromise Policy for Multi-stage Stochastic Linear Programming: Variance and Bias Reduction

This paper focuses on algorithms for multi-stage stochastic linear programming (MSLP). We propose an ensemble method named the “compromise policy”, which not only reduces the variance of the function approximation but also reduces the bias of the estimated optimal value. It provides a tight lower bound estimate with a confidence interval. By exploiting parallel computing, … Read more

Optimizing Vaccine Distribution in Developing Countries under Natural Disaster Risk

For many developing countries, COVID-19 vaccination roll-out programs are not only slow but vaccination centers are also exposed to the risk of natural disaster, like flooding, which may slow down vaccination progress even further. Policy-makers in developing countries therefore seek to implement strategies that hedge against distribution risk in order for vaccination campaigns to run … Read more

Multi-Echelon Inventory Management for a Non-Stationary Capacitated Distribution Network

We present an inventory management solution for a non-stationary capacitated multi-echelon distribution network involving thousands of products. Assuming backlogged sales, we revisit and leverage the seminal multi-echelon inventory management results in the literature to establish the structural properties of the problem, and derive an efficient and practical solution method. In particular, we describe how the … Read more