BIRS Workshop Lecture Videos
Satisficing Models to Mitigate Uncertainty Jaillet, Patrick
Satisficing, as an approach to decision-making under uncertainty, aims at achieving solutions that satisfy the problem's constraints as well as possible. Mathematical optimization problems that are related to this form of decision-making include the P-model of Charnes and Cooper (1963), where satisficing is the objective, as well as chance-constrained and robust optimization problems, where satisficing is articulated in the constraints. In this paper, we first propose the R-model, where satisficing is the objective, and where the problem consists in finding the most "robust" solution, feasible in the problem's constraints when uncertain outcomes arise over a maximally sized uncertainty set. We then study the key features of satisficing decision making that are associated with these problems and provide the complete functional characterization of a satisficing decision criterion. As a consequence, we are able to provide the most general framework of a satisficing model, termed the S-model, which seeks to maximize a satisficing decision criterion in its objective, and the corresponding satisficing-constrained optimization problem that generalizes robust optimization and chance-constrained optimization problems. Next, we focus on a tractable probabilistic S-model, termed the T-model whose objective is a lower bound of the P-model. We show that when probability densities of the uncertainties are log-concave, the T-model can admit a tractable concave objective function. In the case of discrete probability distributions, the T-model is a linear mixed integer program of moderate dimensions. We also show how the T-model can be extended to multi-stage decision-making and present the conditions under which the problem is computationally tractable. Our computational experiments on a stochastic maximum coverage problem strongly suggest that the T-model solutions can be highly effective, thus allaying misconceptions of having to pay a high price for the satisficing models in terms of solution conservativeness. This is joint work with Sanjay Dominik Jena, Tsan Sheng Ng, and Melvyn Sim.
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International