Optimization Online


Satisficing Awakens: Models to Mitigate Uncertainty

Patrick Jaillet(jaillet***at***mit.edu)
Sanjay Dominik Jena(sanjay***at***smart.mit.edu)
Tsan Sheng Ng(isentsa***at***nus.edu.sg)
Melvyn Sim(dscsimm***at***nus.edu.sg)

Abstract: 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.

Keywords: Optimization under uncertainty, Decision-making under uncertainty, Satisficing, Tractable models

Category 1: Stochastic Programming

Category 2: Robust Optimization

Category 3: Integer Programming

Citation: Jaillet, P., S. D. Jena, T. S. Ng, and M. Sim, 01/2016. Satisficing Awakens: Models to Mitigate Uncertainty.

Download: [PDF]

Entry Submitted: 01/28/2016
Entry Accepted: 01/28/2016
Entry Last Modified: 01/28/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society