Chapter 6

Online Optimization—An Introduction

Patrick Jaillet
Laboratory for Information and Decision Systems, Department of Electrical Engineering and Computer Science, and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, jaillet@mit.edu

Michael R. Wagner
Graduate Business Programs, Saint Mary's College of California,Moraga, California 94556, mrw2@stmarys-ca.edu

Abstract
It has been widely recognized (and in some cases for quite a long time) within various communities that there are many situations in which present actions must be made and resources allocated with incomplete knowledge of the future. The difficulty in these situations is that we may have to make our decision based only on the past and the current task we have to perform. It is not even clear how to measure the quality of a proposed decision strategy.The approach usually taken is to devise some probabilistic model of the future and act on this basis. This was the starting point of the theory of Markov decision processes. Other recent approaches—all under the same name, robust optimization—have been proposed, where uncertainty is characterized by set membership, rather than distributions. Online optimization is a different approach, popularized within computer science, and aims at comparing the performance of a strategy that operates with no knowledge of the future (online) with the performance of an optimal strategy that has complete knowledge of the future (offline). In this tutorial, we are proposing to give an overview of the state of the art of this approach—its applications, tools, and techniques—highlighting the relevance to operations research and management science.

Download Chapter 6 - Password-protected content.

The 2010 volume of the TutORials in Operations Research series will be available to people who have registered for the 2010 INFORMS Annual Meeting. All INFORMS members will be able to access TutORials after January 1, 2011. Printed TutORials books from this and previous years can also be ordered here, along with CDs from 2005 to 2009.

For login instructions click here.

________________________________________________

Citation Information:

Jaillet, P., M. R. Wagner. Online optimization—An introduction. J. J. Hasenbein, ed. INFORMS TutORials in Operations Research, Vol. 7. INFORMS, Hanover, MD, pp. 142–152.

Key words: online optimization; uncertainty; competitive analysis; real time