Distributionally robust optimization with multimodal decision-dependent ambiguity sets

Abstract We consider a two-stage distributionally robust optimization (DRO) model with multimodal uncertainty, where both the mode probabilities and uncertainty distributions could be affected by the first-stage decisions. To address this setting, we propose a generic framework by introducing a $$\phi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϕ</mml:mi> </mml:math> -divergence based ambiguity set to characterize the decision-dependent mode probabilities and further consider both moment-based and Wasserstein distance-based ambiguity sets to characterize the uncertainty distribution under each mode. We identify two special $$\phi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϕ</mml:mi> </mml:math> -divergence examples (variation distance and $$\chi ^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>χ</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:math> -distance) and provide specific forms of decision dependence relationships under which we can derive tractable reformulations. Furthermore, we investigate the benefits of considering multimodality in a DRO model compared to a single-modal counterpart through an analytical analysis. Additionally, we develop a separation-based decomposition algorithm to solve the resulting multimodal decision-dependent DRO models with finite convergence and optimality guarantee under certain settings. We provide a detailed computational study over two example problem settings, the facility location problem and shipment planning problem with pricing, to illustrate our results, which demonstrate that omission of multimodality or decision-dependent uncertainties within DRO frameworks result in inadequately performing solutions with worse in-sample and out-of-sample performances under various settings. We further demonstrate the speed-ups obtained by the solution algorithm against the off-the-shelf solver over various instances.