Algorithms for Distributionally Risk-Receptive and Robust Stochastic Integer Programs and Interdiction Problems

Abstract

This dissertation advances the theory and algorithms of stochastic mixed-integer programs under distributional ambiguity, with a particular focus on adversarial games and interdiction problems. We introduce models within both distributionally risk-receptive (DRR) and distributionally robust optimization (DRO) frameworks, allowing for an adjustment of decision-maker's risk attitudes in adversarial settings. A key contribution is the study of an optimistic perspective, modeled by the DRR framework, which complements a pessimistic perspective of the conventional DRO paradigm and offers new insights for analyzing adversarial models. This research considers many algebraic optimization modeling tools such as two-stage and multi-stage stochastic programs, integer and disjunctive programming, decision-independent and decision-dependent uncertainty, and both single- and bi-parameterized recourse problems, in the DRR and DRO frameworks. In particular, the dissertation explores three main directions. In the first direction, we study DRR and DRO two-stage network interdiction problems. For solving them, we propose a new class of cutting planes and develop exact and approximation algorithms with finite convergence results. In the second direction, we extend these frameworks to multi-stage stochastic integer programs with both decision-independent and decision-dependent uncertainty, and introduce solution methods based on cutting plane and reformulation techniques. We further extend these results to multi-stage stochastic disjunctive programs by introducing an extended formulation for their feasible sets. These models are demonstrated on multi-period interdiction problems for network vulnerability assessment. In the third direction, we study two-stage stochastic integer programs with bi-parameterized recourse, where both the recourse objective and constraints are parameterized by first-stage decisions, under both min-min and min-max structures. These models arise in general interdiction problems, decision-dependent stochastic programs, and DRO problems with decision-dependent ambiguity sets that may be empty for some first-stage decisions. To solve these problems, we propose Lagrangian-integrated L-shaped (L^2) methods, including both exact and approximation variants. Our numerical experiments demonstrate that the proposed methods outperform existing approaches, achieving significant speedups in solving interdiction problem instances and general stochastic programming problem instances. Furthermore, through out-of-sample tests, we show that the DRR framework can effectively identify network vulnerabilities and provide robust solutions under data contamination.