Servizi per la didattica
PORTALE DELLA DIDATTICA

Graphs and Combinatorial Optimization

01UEPRP

A.A. 2018/19

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
2018/19
PERIOD: JUNE 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).
PERIOD: JUNE 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).
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).
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).
The lectures will be held in room DIGEP B on the following dates: 12/06/2019: 14:00-16:00. 14/06/2019: 14:00-16:00. 19/06/2019: 14:00-16:00. 21/06/2019: 14:00-16:00. 27/06/2019: 14:00-16:00. 28/06/2019: 14:00-16:00. 3/07/2019: 14:00-16:00. 5/07/2019: 14:00-16:00. 10/07/2019: 14:00-16:00. 12/07/2019: 14:00-16:00.
The lectures will be held in room DIGEP B on the following dates: 12/06/2019: 14:00-16:00. 14/06/2019: 14:00-16:00. 19/06/2019: 14:00-16:00. 21/06/2019: 14:00-16:00. 27/06/2019: 14:00-16:00. 28/06/2019: 14:00-16:00. 3/07/2019: 14:00-16:00. 5/07/2019: 14:00-16:00. 10/07/2019: 14:00-16:00. 12/07/2019: 14:00-16:00.
Modalità di esame:
Exam:
...
Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.
Exam:
In addition to the message sent by the online system, students with disabilities or Specific Learning Disorders (SLD) are invited to directly inform the professor in charge of the course about the special arrangements for the exam that have been agreed with the Special Needs Unit. The professor has to be informed at least one week before the beginning of the examination session in order to provide students with the most suitable arrangements for each specific type of exam.
Esporta Word
© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
Contatti