Interdiction Games on Markovian PERT Networks

In a stochastic interdiction game a proliferator aims to minimize the expected duration of a nuclear weapons development project, and an interdictor endeavors to maximize the project duration by delaying some of the project tasks. We formulate static and dynamic versions of the interdictor's decision problem where the interdiction plan is either precommitted or adapts to new information revealed over time, respectively. The static model gives rise to a stochastic program, whereas the dynamic model is formalized as a multiple optimal stopping problem in continuous time and with decision-dependent information. Under a memoryless probabilistic model for the task durations, we prove that the static model reduces to a mixed-integer linear program, whereas the dynamic model reduces to a finite Markov decision process in discrete time that can be solved via efficient value iteration. We then generalize the dynamic model to account for uncertainty in the outcomes of the interdiction actions. We also discuss a crashing game where the proliferator can use limited resources to expedite tasks so as to counterbalance the interdictor's efforts. The resulting problem can be formulated as a robust Markov decision process.

"Dice"-sion Making under Uncertainty: When Can a Random Decision Reduce Risk?

Daniel Kuhn, Wolfram Wiesemann

Stochastic programming and distributionally robust optimization seek deterministic decisions that optimize a risk measure, possibly in view of the most adverse distribution in an ambiguity set. We investigate under which circumstances such deterministic decisions are strictly outperformed by random decisions which depend on a randomization device producing uniformly distributed samples that are independent of all uncertain factors affecting the decision problem. We find that in the absence of distributional ambiguity, deterministic decisions are optimal if both the risk measure and the feasible region are convex, or alternatively if the risk measure is mixture-quasiconcave. We show that several classes of risk measures, such as mean (semi-)deviation and mean (semi-)moment measures, fail to be mixture-quasiconcave and can therefore give rise to problems in which the decision maker benefits from randomization. Under distributional ambiguity, on the other hand, we show that for any ambiguity averse risk measure there always exists a decision problem (with a nonconvex—e.g., mixed-integer—feasible region) in which a randomized decision strictly dominates all deterministic decisions.

2019

Primal and dual linear decision rules in stochastic and robust optimization

Daniel Kuhn, Wolfram Wiesemann

Linear stochastic programming provides a flexible toolbox for analyzing real-life decision situations, but it can become computationally cumbersome when recourse decisions are involved. The latter are usually modeled as decision rules, i.e., functions of the uncertain problem data. It has recently been argued that stochastic programs can quite generally be made tractable by restricting the space of decision rules to those that exhibit a linear data dependence. In this paper, we propose an efficient method to estimate the approximation error introduced by this rather drastic means of complexity reduction: we apply the linear decision rule restriction not only to the primal but also to a dual version of the stochastic program. By employing techniques that are commonly used in modern robust optimization, we show that both arising approximate problems are equivalent to tractable linear or semidefinite programs of moderate sizes. The gap between their optimal values estimates the loss of optimality incurred by the linear decision rule approximation. Our method remains applicable if the stochastic program has random recourse and multiple decision stages. It also extends to cases involving ambiguous probability distributions.

2011

Generalized Decision Rule Approximations for Stochastic Programming via Liftings

Daniel Kuhn, Wolfram Wiesemann

Stochastic programming provides a versatile framework for decision-making under uncertainty, but the resulting optimization problems can be computationally demanding. It has recently been shown that, primal and dual linear decision rule approximations can yield tractable upper and lower bounds on the optimal value of a stochastic program. Unfortunately, linear decision rules often provide crude approximations that result in loose bounds. To address this problem, we propose a lifting technique that maps a given stochastic program to an equivalent problem on a higher-dimensional probability space. We prove that solving the lifted problem in primal and dual linear decision rules provides tighter bounds than those obtained from applying linear decision rules to the original problem. We also show that there is a one-to-one correspondence between linear decision rules in the lifted problem and families of non-linear decision rules in the original problem. Finally, we identify structured liftings that give rise to highly flexible piecewise linear decision rules and assess their performance in the context of a stylized investment planning problem.

Springer Verlag2015