University of Cagliari
Meta-heuristics for Combinatorial Optimization
28 February 2012
Scuola di Dottorato in Scienze Matematiche e Informatiche
Scuola di Dottorato in Ingegneria del Territorio
Il Professor Teodor Gabriel Crainic, University of Quebec -Montreal completerà il ciclo di seminari sul tema:
Meta-heuristics for Combinatorial Optimization
con il seguente calendario:
III- martedi’ 28 febbraio h 16 - 18
IV- mercoledi’ 29 febbraio h 16 - 18
tutti i seminari si svolgeranno presso il Dipartimento di Matematica e Informatica, via Ospedale 72, aula F, piano terra.
ABSTRACT: Many decision issues associated to planning complex systems in, e.g., transportation, logistics, telecommunication, production and so on involve performing constrained choices among sets of alternatives to optimize a given objective. In Operations Research, these issues are generally viewed as combinatorial optimization problems and are represented through integer or mix-integer formulations. Most combinatorial optimization problems are formally difficult. Moreover, most applications of interest yield large-scale models. Approximate solution methods, meta-heuristics in particular, are then the methodology of choice in addressing these problems.
The series of four lectures will explore meta-heuristic solution methods for combinatorial optimization problems. We will examine classical heuristics, neighbourhood and population-based meta-heuristics. Two major classes of problems, vehicle routing and network design will be used to illustrate the concepts and methods.
1 & 2. Problem solving and approximate solution methods
A brief return on why we need approximate solution methods and what are those. From simple heuristics to local search and meta-heuristics. Model-based heuristics. Network design. Classical heuristics, Vehicle routing.
3. Neighbourhood-based meta-heuristics
Principles and components. Tabu Search, GRASP, VNS, Adaptive large neighborhood search.
4. Population-based meta-heuristics
Principles and components. Genetic algorithms, Scatter Search and Path Relinking.
Teodor Gabriel Crainic, Ph.D., FRSC
Professor of Operations Research, Logistics and Transportation School of Business Management, Université du Québec à Montréal Director, Intelligent Transportation Systems Laboratory Interuniversity Centre on Enterprise Networks, Logistics and Transportation (CIRRELT) Montreal, Canada.
per informazioni:
Massimo Di Francesco, mdifrance@unica.it
Michela Lai, mlai@unica.it
Giovanni M. Sechi, sechi@unica.it
Paola Zuddas, zuddas@unica.it