Thesis Defense
"Amsaa: an Anticipatory Algorithm for Online Stochastic Combinatorial Optimization"
Luc Mercier
Wednesday, September 24, 2008 at 4:00 P.M.
Room 368 (CIT 3rd floor)
Online stochastic combinatorial optimization problems are problems in which a decision maker is trying to minimize or maximize an objective by making a sequence of discrete decisions, while acquiring information over time, and in face of an uncertain future. Two examples are:
- the scheduling of drug development tasks in a pharmaceutical company, where a decision maker has to manage costly human and material resources in face of uncertainty regarding the efficiency of drugs
- the scheduling of polymerizations in a polystyrene factory, where reactors can be used to produce different varieties of polystyrene, and future demands are uncertain
We study decision making in limited time for such online stochastic combinatorial optimization problems, and focus on anticipatory algorithms, a class of algorithms that relaxes constraints due to the timing of information acquisition by the decision maker. A first question we investigate is why a specific heuristic based on this simplification perform sometimes very well.
We then turn on to problems such as the two aforementioned ones on which this heuristic produces largely suboptimal decisions. To address these problems, we then propose Amsaa, the anytime multistep anticipatory algorithm, that in addition to attractive characteristics of previous anticipatory algorithms is guaranteed to produce optimal decisions with enough computation time. Empirical results show that Amsaa outperforms existing approaches on the stochastic project scheduling problem and on the polystyrene production planning problem. In particular, Amsaa scales thousands of time better than a stochastic programming approach in the project scheduling problem.
Host: Pascal Van Hentenryck
| Page Owner: Webmaster | Last Modified: Tue Sep 2 08:52:56 2008 |