Wasserstein distributionally robust optimization (DRO) is a versatile and widely adopted framework for decision-making under uncertainty, yet its standard deterministic reformulations generally contain non-convex inner subproblems that are challenging to solve. To address this issue, we propose a shrinkage path heuristic that reduces the solution of a DRO problem to a one-dimensional search over the line segment connecting the (typically benign) sample average approximation (SAA) and the (more demanding but practically solvable) classical robust optimization solution. We derive a priori suboptimality bounds in stylized settings and, for the general case, a posteriori bounds obtained by applying a similar heuristic to a dual formulation. Numerical experiments on a multi-item newsvendor and an appointment scheduling problem show that the shrinkage path heuristic attains 85-110% (resp. 45-70%) of the out-of-sample performance improvements of Wasserstein DRO over SAA, at a fraction of the computational cost.
Ling-Jun Meng, Ryan Cory-Wright, W. Wiesemann· 0 citations
Off-the-Shelf Solvers Take on the Curse of Dimensionality
Many real-world decision problems—from managing power plants and microgrids to coordinating fleets of robots, recommender systems, and traffic networks—involve dynamics and rewards that decompose into smaller, loosely interacting components. Factored Markov decision processes (FMDPs) exploit this structure to escape the curse of dimensionality, but they have traditionally been solved with bespoke algorithms that require painstaking implementation and substantial fine-tuning. In this issue, Liu, Wiesemann, and Yue introduce a new mathematical programming perspective on FMDPs that swaps hand-crafted machinery for off-the-shelf optimization solvers. By encoding sparse dependencies through mixed-integer linear programming–representable feature vectors, their formulation exploits factored structure in both states and actions, unifies and extends existing treatments of context-specific independence, and pairs an approximate linear program with a novel cutting-plane algorithm. Companion feature-learning and dynamic-basis routines further enhance scalability, and computational experiments across stylized and operational case studies illustrate the method’s promise.
Huikang Liu, W. Wiesemann, Man-Chung Yue· Operational Research· 0 citations
