Distributionally Ambiguous Multistage Stochastic Integer and Disjunctive Programs: Applications to Sequential Two-player Interdiction Games

This paper studies the generalizations of multistage stochastic mixed-integer programs (MSIPs) with distributional ambiguity, namely distributionally risk-receptive and risk-averse multistage stochastic mixed-integer programs (denoted by DRR- and DRA-MSIPs). These modeling frameworks have applications in non-cooperative Stackelberg games involving two players, namely a leader and a follower, with uncertainty in the impact of the decisions made by the leader. We present cutting plane-based and reformulation-based approaches for solving DRR- and DRA-MSIPs to optimality. We showcase that these approaches are finitely convergent with probability one. We also introduce generalizations of MSIPs by considering multistage stochastic disjunctive programs with(out) distributional ambiguity and present algorithms for solving them. To assess the performance of the algorithms for MSIPs, we consider instances of multistage maximum flow and facility location interdiction problems that are important interdiction problems in their own right, and only their single-stage variants have been studied in the literature. Based on our computational results, we observe that the cutting plane-based approaches are 26.1 times (on average) faster than the reformulation-based approaches for the foregoing instances.

Article

Download

View Distributionally Ambiguous Multistage Stochastic Integer and Disjunctive Programs: Applications to Sequential Two-player Interdiction Games