Title: On some tractable optimization models dealing with uncertainty
Speaker: Prof. Patrick Jaillet
Affiliation: Laboratory for Information and Decision Systems – MIT
Location: LG19 seminar room Business School
Time: 12:00pm
Abstract. In the first part of the talk we consider the minmax regret model for combinatorial optimization problems under uncertainty, which can be viewed as a zero-sum game played between an optimizing player and an adversary, where the optimizing player selects a solution and the adversary selects costs with the intention of maximizing the regret of the player. The conventional model considers only deterministic solutions/strategies, and minmax regret versions of most polynomial solvable problems are NP-hard. In this talk, we consider a randomized model where the optimizing player selects a probability distribution (corresponding to a mixed strategy) over solutions and the adversary selects costs with knowledge of the player’s distribution, but not its realization. We show that under this randomized model, the minmax regret version of any polynomial solvable combinatorial problem becomes polynomial solvable. This holds true for both interval and discrete scenario representations of uncertainty. In the second part of the talk we consider satisficing models, which, as an approach to decision-making under uncertainty, aims at achieving solutions that satisfy the problem’s constraints as much 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 talk, we introduce 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. We then focus on a tractable probabilistic S-model, termed the T-model whose objective is a lower bound of the P-model.
About the speaker. Patrick Jaillet is the Dugald C. Jackson Professor in the Department of Electrical Engineering and Computer Science and a member of the Laboratory for Information and Decision Systems at MIT. He is also one of the two Directors of the MIT Operations Research Center. Before MIT, he held faculty positions at the University of Texas at Austin and at the Ecole Nationale des Ponts et Chaussees, Paris. He received a Diplôme d’Ingénieur from France, and a PhD in Operations Research from MIT. His current research interests include on-line and data-driven optimization under uncertainty. He is a Fellow of INFORMS and a member of SIAM.