Applicazioni di Ottimizzazione Discreta (2.5 crediti per Laurea Specialistica; 5 crediti per Dottorato)
Corso Monografico
Nel corso vengono analizzati approfonditamente casi reali di applicazione dell'ottimizzazione discreta. In particolare verranno curati nel dettaglio la modellizzazione e gli aspetti pratici di soluzione. Non è richiesto alcun prerequisito se non il corso di Fondameti di Ricerca Operativa. Di volta in volta si sceglieranno le applicazioni più significative e di attualità nel campo dell'informatica delle telecomunicazioni, dei trasporti, della logistica e della finanza.
Edizione 2008: Applicazioni di ottimizzazione discreta nelle telecomunicazioni
Discrete Optimization in Telecommunications (PhD level)
Prof. Di Yuan
Aim
The course is aimed at providing the participants with knowledge
in optimization problems in planning wireline and wireless telecommunication
networks, as well as optimization models and methods that are
of interest for solving these problems. The course aims also at
providing training in developing efficient discrete mathematical
models and methods
Scope
A comprehensive coverage of problem types in telecommunication
network planning
Mathematical modeling focusing on model efficiency, i.e., how
to represent discrete optimization problems by models that enable
computationally efficient solution approaches
How general concepts and principles of discrete optimization (e.g.,
decomposition, cutting plane) can be adapted to the problems in
the subject area of the course
Prerequisites
The participants are expected to be familiar with basics of linear
programming, linear integer programming, and combinatorial optimization.
Knowledge in telecommunication networks is not a requirement.
Contents
Optimization models and methods for
multi-commodity network design problems, including uncapacitated
network design, capacitated network design, and network loading
optimal routing and wavelength assignment in optical networks
optimal routing with multi-commodity flow
optimization of IP routing
frequency assignment in mobile cellular networks
base station location and coverage planning in 3G/UMTS networks
link scheduling and cross-layer optimization in wireless multi-hop
networks
minimum-energy broadcast and multicast in wireless ad hoc networks
Application of general concepts in optimization to the problems
above, including
linear programming (LP), duality, column generation
linear integer programming: LP relaxation, cutting plane, branch-and-bound,
branch-and-cut, branch-and-price, Lagrangean duality
network flow and algorithms: shortest path, maximum flow, minimum-cost
flow, MST
primal and dual decomposition methods
heuristics
Provisional dates (for times and rooms refer to the MS in Computer Engineering schedule): April 1, 3, 8, 10, 15, 17, 22; May 22, 27, 29; June: 3, 5, 6
Edizione 2007: Applicazioni di ottimizzazione discreta in medicina e nei trasporti
Docenti: H. W. Hamacher (Optimization group, Univ. Kaiserslautern)
Goal of the course
Many important practical problems can be solved with fast and
reliable algorithms using explicitly or implicitly network flow
algorithms. While the solution of explicit network flow problems
is part of any course on operations research, optimization, or
algorithms, the potential for detecting and solving implicit network
flow or "hidden flow" problems is mostly not discussed
in these lectures. The goal of this course is to close this gap
and simultaneously cover several important applications.
Program
Two practical problems: Cancer radiation and the location of
stops in public transportation
Consecutive ones (C1) matrices and their use in solving (integer)
linear programs
Decomposition of integer matrices into C1 matrices
Polynomial algorithms for decomposition time (DT) problem
NP-completeness of decomposition cardinality (DC) problem
Integer programming models and heuristics for DC
Solving (binary) linear programs by (semi-)simultaneous network
flows
Using decomposition to tackle the practical problems of (1) in
a multi-objective environment.
The course will be based on joint research work with Ravi Ahuja (University of Florida, USA), Davaatseren Baatar and Natshia Boland (University of Melbourne, Australia), Alexander Engau (University of Clemson, USA), Frank Lenzen (Accenture Consulting, Germany)), Stefan Ruzika (University of Kaiserslautern, Germany), Anita Schöbel (University of Goettingen, Germany), and Dorothea Wagner (University of Karlsruhe, Germany).
Lectures
Monday 14:15-16:15 B52
Tuesday 16:15-18:15 D22
Wednesday !6:15-18:15 B53
Edizione 2006: Routing and Scheduling problems
Docenti: Luca Maria Gambardella & Monaldo Mastrolilli
(IDSIA Lugano)
sito
aggiornato del corso con materiale didattico
Per alcuni problemi classici di routing e di scheduling vengono presentate diverse tecniche di risoluzione. In particolare vengono descritti algoritmi approssimati costruttivi e/o basati sulla ricerca locale. Per alcuni esempi viene fornito a complemento un'analisi nel caso peggiore della qualità della soluzione ottenuta e della complessità temporale. Alcune applicazioni industriali vengono presentate nei diversi settori.
Introduction to VRP Problems;
VRP models, Capacitated, Time Windows, Pick-Up and Delivery, Relations
with TSP;
Constructive VRP heuristics: Nearest Neighbor, Double Ended, Multiple
Fragment, Christofides, Clarke-Wright Saving, Angle, Space Filling
Curve, Composite methods (Routing + Clustering);
Local searches for VRP: 2opt, 3opt, Customers relocation, Crossover,
Customers exchange, path exchange;
Meta Heuristics for VRP: Simulated Annealing, Tabu Search, Genetic
Algorithms, Ant Colony Optimization;
Industrial Vehicle Routing Applications: Pina Petroli, Migros,
Number1;
Introduction to scheduling problems;
Scheduling Problem models: Single Machine Sequential Ordering
Problems, Identical parallel machines, Uniform parallel machines,
Unrelated parallel machines, Shop problems;
Constructive and Greedy heuristics;
Local searches: Jump, Swap, Push, Shift, SOP-3-Exchange;
Meta Heuristics: Simulated Annealing, Tabu search, Genetic Algorithms,
Ant Colony Optimization
Polynomial time approximation schemes;
Industrial Application: MCM;
Modalità d'esame
Orale, con la possibilità di presentare un articolo
della letteratura del settore.
Edizione 2005: Modelli e metodi di ottimizzazione per la biologia computazionale
Docente: Giuseppe Lancia - Università di Udine
Rassegna dei principali ambiti applicativi nel settore della biologia molecolare computazionale e descrizione di modelli matematici e metodi di ottimizzazione che permettono di affrontare con successo alcuni problemi rilevanti.