Roberto Montemanni
Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA)
Lugano-Manno, Switzerland
Abstract:
Mathematical models often assume the precise knowledge of some information related to the modelled phenomenon (e.g. travel times in the case of the shortest path problem). Estimating this kind of data exactly is typically a difficult task, since these data usually depend on factors that are difficult to predict (e.g. traffic jams in case of travel times on a road network). For this reason the classic model, where an estimate has to be given for partially unknown data, might lead to a solution that is far away from the real optimum, with respect with the real (unknown) data.
To overcome this undesired phenomenon, more complex models that take into account uncertainty about read data have to be considered. The scenario model represents then uncertainty through a finite set of equally possible alternative realizations of the data, that are taken into account simultaneously. Alternatively, a model where an interval of possible values is associated with each input data, the so-called interval data model has been studied.
The aim of this talk is to present recent advances in the field of robust optimization with interval data. In particular, application to classic combinatorial optimization problems will be presented.
For many applications, interval data models tend to be too conservative. This aspect will be discussed, and solutions to mitigate this over-conservative behaviour will be finally proposed.
(joint work with L.M. Gambardella, A.V. Donati and J. Barta)