On Finite Adaptability in Two-Stage Distributionally Robust Optimization.

The paper by Han, Bandi, and Nohadani on "On Finite Adaptability in Two-Stage Distributionally Robust Optimization" studies finite adaptability with the goal to construct interpretable and easily implementable policies in the context of two-stage distributionally robust optimization problems. To achieve this, the set of uncertainty realizations needs to be partitioned. The authors show that an optimal partitioning can be accomplished via "translated orthants." They then propose a nondecreasing orthant partitioning and binary approximation to obtain the corresponding "orthant-based policies" from a mixed-integer optimization problem of a moderate size. For these policies, they provide provable performance bounds, generalizing the existing bounds in the literature. For more general settings, they also propose optimization formulations to obtain posterior lower bounds that can serve to evaluate performance. Two numerical experiments support these findings. A joint inventory-routing problem highlights the practical applicability for large-sized instances with mixed-integer recourse. A case study from a pharmacy retailer demonstrates that the orthant-based policies are less sensitive to cost parameters than optimal solutions, enabling these policies to outperform comparable methods when the realized cost ratio deviates from its nominal value. In many real applications, practitioners prefer policies that are interpretable and easy to implement. This tendency is magnified in sequential decision-making settings. In this paper, we leverage the concept of finite adaptability to construct policies for two-stage optimization problems. More specifically, we focus on the general setting of distributional uncertainties affecting the right-hand sides of constraints, because in a broad range of applications, uncertainties do not affect the objective function and recourse matrix. The aim is to construct policies that have provable performance bounds. This is done by partitioning the uncertainty realization and assigning a contingent decision to each piece. We first show that the optimal partitioning can be characterized by translated orthants, which only require the problem structure and hence are free of modeling assumptions. We then prove that finding the optimal partitioning is hard and propose a specific partitioning scheme with orthants, allowing the efficient computation of orthant-based policies via solving a mixed-integer optimization problem of a moderate size. By leveraging the geometry of this partitioning, we provide performance bounds of the orthant-based policies, which also generalize the existing bounds in the literature. These bounds offer multiple theoretical insights on the performance, for example, its independence on problem parameters. We also assess suboptimality in more general settings and provide techniques to obtain lower bounds. The proposed policies are applied to a stylized inventory routing problem with mixed-integer recourse. We also study the case of a pharmacy retailer by comparing alternative methods regarding computational performance and robustness to parameter variation. Funding: E. Han is funded by the Southern Methodist University start-up fund for this research. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2022.2273. [ABSTRACT FROM AUTHOR]