avviso seminario

[Rita Abbondanza <rita@iac.rm.cnr.it>]

ISTITUTO APPLICAZIONI CALCOLO "M. PICONE"
Viale del Policlinico 137
Roma

Avviso Seminario:


Titolo: Convergence results on general-purpose algorithms for stochastic combinatorial problems

Relatore/i: Prof. W. GUTJAHR  (Dept. of Statistics and Decision Support Systems, University of Vienna (Austria))

Data: venerdi' 11 aprile 2003,  ore  15.00

ABSTRACT: 
In many real-world applications, combinatorial optimization problems have to be solved under uncertainty, i.e., with parameter values not known exactly. In such cases, stochastic models can be applied; usually, the aim is then to optimize the expected value of the objective function under given constraints. If already the deterministic boundary case of the problem is computationally hard, such that it can only be solved heuristically for reasonable instance sizes, heuristics are required for the stochastic case all the more. The talk investigates the question under what conditions heuristics for the stochastic problem are able to converge to the exact optimal solution. For two stochastic optimization metaheuristics, a "stochastic" variant of Simulated Annealing and Stochastic Branch and Bound, theoretical convergence results are recapitulated. Finally, two types of ACO (Ant Colony Optimization) algorithms for stochastic optimization are outlined, and for one of them, a convergence result with promising implications concerning runtime behavior is outlined. 


Sede: IAC - Aula II piano 

Per ulteriori informazioni rivolgersi a: Dr. G. Sebastiani
(sebastiani@iac.rm.cnr.it)