The Value of Adaptability

Constantine Caramanis
Department of Electrical Engineering and Computer Science
Massachusetts Institute of Technology


Wednesday, October 12, 2005
4:30 - 5:45 PM
Terman Engineering Center, Room 453


Abstract:

We consider linear optimization problems with parameter uncertainty, under a deterministic model for the uncertainty. This is known as robust optimization. Under the robust optimization paradigm, a decision maker selects a single robust solution that is immunized against parameter uncertainty. We consider a departure from this paradigm, allowing the decision-maker some limited, finite adaptability. Here, the decision-maker can obtain some additional information about the uncertainty before committing to a decision. We propose a hierarchy of increasing adaptability that bridges the gap between the robust formulation, and the re-optimization (or fully adjustable) formulation. The central problem we address is optimally structuring this adaptability, and understanding its marginal value. In contrast to the model of affine adaptability proposed by Ben-Tal et al., our proposed framework can accommodate discrete variables. In terms of performance for continuous linear optimization, the two frameworks are complementary, in the sense that we provide examples where the proposed framework yields stronger solutions, and vice versa.

In this talk, we give some geometric results that characterize the benefit of k-adaptability, and furthermore give necessary conditions that ``good information,'' or ``good adaptability,'' must satisfy. We give some complexity results about optimally structuring finite adaptability, and then consider some algorithms, examples, and computational results.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html