Prof. Martin Groetschel
Konrad-Zuse-Zentrum and Technische Universitaet
Berlin, Germany
Sexta-feira, 7 de maio de 1999, 15:00 c.t.
Abstract:
In ``classical'' optimization, all data of a problem instance are considered given. The standard theory and the usual algorithmic techniques apply to such cases only. Online optimization is different. Many decisions have to be made before all data are available. In adddition, decisions once made, cannot be changed. How should one act ``best'' in such an environment?
In this talk I will survey online problems coming up in combinatorial optimization. I will focus on real-world applications and report, in particular, on problems arising in transportation and the control and optimization of material handling systems. I will outline theoretical ways to analyse online problems (e.g., the concept of competitiveness); but I will also show what can be (and is) done in practice. Online optimization is a field wide open for innovative research and modelling. In practical situations it is often not clear what really is to be optimized, thus, often auxiliary problems are considered that reflect a compromise between various points of view. Similarly, it is not apparent what an optimal online strategy is. I will also discuss such issues.