Servizi per la didattica
PORTALE DELLA DIDATTICA

Graphs and Combinatorial Optimization

01UEPRP

A.A. 2020/21

Course Language

Inglese

Degree programme(s)

Doctorate Research in Gestione, Produzione E Design - Torino

Course structure
Teaching Hours
Lezioni 20
Lecturers
Teacher Status SSD h.Les h.Ex h.Lab h.Tut Years teaching
Scatamacchia Rosario   Ricercatore a tempo det. L.240/10 art.24-B MAT/09 20 0 0 0 2
Co-lectuers
Espandi
Context
SSD CFU Activities Area context
*** N/A ***    
Date d'appello
Orario delle lezioni
Statistiche superamento esami
L’emergere di nuovi paradigmi tecnologici e la disponibilità di consistenti quantità di informazioni pongono al giorno d’oggi sfide sempre più complesse nei processi decisionali. Lo scopo del corso è quello di fornire strumenti utili per la risoluzione di problemi di ottimizzazione in contesti differenti attraverso metodi avanzati della Teoria dei Grafi e dell’Ottimizzazione Combinatoria. Più precisamente, il corso si propone di illustrare algoritmi su grafo e approcci generali di risoluzione basati sulla programmazione matematica, programmazione dinamica, tecniche di decomposizione e algoritmi randomizzati. L’obiettivo principale è quello di fornire le conoscenze base per l’applicazione di tali approcci per problemi industriali di diversa natura, tra cui problemi di allocazione di risorse, di ottimizzazione di reti di trasporto e di telecomunicazioni, di pianificazione della produzione. Saranno anche discussi algoritmi per la risoluzione di problemi paradigmatici dell’ottimizzazione combinatoria (3-SAT, Knapsack, Min/Max Cut). Il corso sarà tenuto in lingua inglese e si prevede di erogarlo in presenza in aula. Allo stesso tempo, si prevede la possibilità di tenere le lezioni a distanza se non sarà possibile farlo in presenza. Per gli studenti che non potranno seguire le lezioni in presenza, verranno fornite le slide del corso e del materiale di testo aggiuntivo e saranno previste delle sessioni interattive con il docente per la discussione degli argomenti del corso.
The development of new technologies and the availability of huge quantities of collected data pose nowadays more and more complex challenges in the decisional processes. The course aims to provide essential tools for solving optimization problems arising in different contexts throughout advanced methods from Graph Theory and Combinatorial Optimization. More precisely, we will illustrate general graph algorithms and solution methods based on mathematical programming, dynamic programming, decomposition techniques and randomized algorithms. The main goal is to provide the basic skills for the application of the considered approaches to industrial problems of different nature such as, among others, resource allocation problems, transportation and telecommunications problems, production planning problems. We will also discuss algorithms for paradigmatic problems in combinatorial optimization (3-SAT, Knapsack, Min/Max Cut). The lessons are supposed to be held in a classroom. If in-person teaching is not possible, online teaching will be guaranteed. Slides, additional notes and online interactive sessions with the teacher will be provided to students who will not be able to attend the lessons.
Conoscenze base di algebra lineare e di teoria della probabilità.
Basic knowledge of linear algebra and probability theory.
Introduzione alla Programmazione Lineare: • Modelli di programmazione lineare, algoritmo del simplesso e teoria della dualità. • Tecniche di decomposizione per problemi di programmazione lineare mista (intera/continua): - Column Generation e Dantzig-Wolfe Decomposition. - Benders’ Decomposition. Introduzione alla teoria dei grafi: • Concetti di base. • Algoritmi per problemi paradigmatici (cammini minimi, alberi ricoprenti). Programmazione Dinamica: • Funzioni ricorsive. • Algoritmi di base e avanzati. Algoritmi randomizzati: • Analisi di performance attesa. • Esempi applicativi per problemi di logica booleana (3-SAT) e di teoria dei grafi (Min/Max cut).
Introduction to Linear Programming: • Linear programming models, simplex algorithm and duality theory. • Decomposition techniques for Mixed Integer Linear Programming problems: - Column Generation and Dantzig-Wolfe Decomposition. - Benders’ Decomposition. Introduction to graph theory: • Basic concepts. • Algorithms for paradigmatic problems (shortest paths, spanning tree). Dynamic Programming: • Recursion functions. • Standard and advanced algorithms. Randomized algorithms: • Expected performance analysis. • Applications to boolean satisfiability problems (3-SAT) and problems from graph theory (Min/Max cut).
In presenza
On site
Presentazione orale
Oral presentation
P.D.1-1 - Novembre
P.D.1-1 - November
© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
Contatti