Servizi per la didattica
PORTALE DELLA DIDATTICA

Ottimizzazione per il problem solving

01QNKOA, 01QNKJM, 01QNKLI, 01QNKLM, 01QNKLN, 01QNKLP, 01QNKLS, 01QNKLX, 01QNKLZ, 01QNKMA, 01QNKMB, 01QNKMC, 01QNKMH, 01QNKMK, 01QNKMN, 01QNKMO, 01QNKMQ, 01QNKNX, 01QNKOD, 01QNKPC, 01QNKPN

A.A. 2020/21

Lingua dell'insegnamento

Italiano

Corsi di studio

Corso di Laurea in Ingegneria Informatica - Torino
Corso di Laurea in Ingegneria Meccanica (Mechanical Engineering) - Torino
Corso di Laurea in Ingegneria Dell'Autoveicolo (Automotive Engineering) - Torino
Corso di Laurea in Ingegneria Informatica (Computer Engineering) - Torino
Corso di Laurea in Ingegneria Dell'Autoveicolo - Torino
Corso di Laurea in Electronic And Communications Engineering (Ingegneria Elettronica E Delle Comunicazioni) - Torino
Corso di Laurea in Ingegneria Dei Materiali - Torino
Corso di Laurea in Ingegneria Elettrica - Torino
Corso di Laurea in Ingegneria Aerospaziale - Torino
Corso di Laurea in Ingegneria Biomedica - Torino
Corso di Laurea in Ingegneria Chimica E Alimentare - Torino
Corso di Laurea in Ingegneria Civile - Torino
Corso di Laurea in Ingegneria Edile - Torino
Corso di Laurea in Ingegneria Energetica - Torino
Corso di Laurea in Ingegneria Meccanica - Torino
Corso di Laurea in Ingegneria Per L'Ambiente E Il Territorio - Torino
Corso di Laurea in Matematica Per L'Ingegneria - Torino
Corso di Laurea in Ingegneria Elettronica - Torino
Corso di Laurea in Ingegneria Fisica - Torino
Corso di Laurea in Ingegneria Del Cinema E Dei Mezzi Di Comunicazione - Torino
Corso di Laurea in Design E Comunicazione Visiva - Torino

Organizzazione dell'insegnamento
Didattica Ore
Docenti
Docente Qualifica Settore h.Lez h.Es h.Lab h.Tut Anni incarico
Collaboratori
Espandi

Didattica
SSD CFU Attivita' formative Ambiti disciplinari
MAT/09 6 D - A scelta dello studente A scelta dello studente
2018/19
Il corso di Ottimizzazione per il Problem Solving permette di affrontare e risolvere una vasta gamma di problemi di decisione propri dell’ingegneria o di altri settori del mondo reale: informatica, telecomunicazioni, industria manifatturiera, trasporti, logistica, economia, management, finanza, energia, terziario ed altri ancora. L’ottimizzazione richiede la modellazione del problema allo studio, cioè la costruzione di un modello matematico, sufficientemente rappresentativo del problema stesso, costituito dalle variabili del problema e da un obiettivo da perseguire nel rispetto di opportuni vincoli. Questo modello viene quindi risolto mediante opportuni algoritmi e solver di ottimizzazione.
The course Optimization for Problem Solving allows to face and solve a wide range of decision problems in engineering or other areas of the real world: information technology, telecommunications, manufacturing, transportation, logistics, economics, management, finance, energy, services, and others. The optimization requires modeling of the problem to the study, namely the construction of a mathematical model which is sufficiently representative of the problem itself. This model is constituted by variables, objective function and appropriate constraints to be satisfied. The above model is then solved by suitable algorithms and optimization solvers.
Conoscenze che l’insegnamento si propone di trasmettere agli studenti: gli studenti approfondiranno la teoria, i metodi e gli algoritmi per la risoluzione di problemi di ottimizzazione lineare continua (cioè, dove le variabili sono continue) e di flussi su reti. Verranno forniti alcuni cenni di ottimizzazione lineare intera (cioè, dove le variabili sono intere). Abilità che l’insegnamento si propone di trasmettere agli studenti: gli studenti svilupperanno l’abilità di costruire, dato un problema reale, un corrispondente ed adeguato modello matematico e risolverlo mediante opportuni algoritmi e solver di ottimizzazione. Gli studenti acquisiranno il corretto approccio al problem solving, che potranno proficuamente utilizzare nelle più svariate situazioni decisionali della loro vita.
Knowledge that the course aims to provide students with: students will explore the theory, methods, and algorithms for solving linear continuous optimization problems (i.e., where the variables are continuous) and flows on networks. Outline of linear integer optimization problems (i.e., where the variables are integer) will be also given. Skills that the course aims to provide students with: students will develop skills to construct, given real-life problems, corresponding and adequate mathematical models and solve them using appropriate algorithms and optimization solvers.
Non sono richiesti prerequisiti. Le uniche conoscenze pregresse sono quelle già acquisite nei corsi di base.
No prerequisites are required. The only prior knowledge are those already acquired in the first years courses.
1. Ottimizzazione lineare continua: problemi e modelli, metodo del simplesso e derivati, dualità (40% del corso). 2. Analisi della complessità computazionale dei problemi decisionali (5%). 3. Flussi su reti: concetti fondamentali di teoria dei grafi, ricerca di un albero ricoprente di costo minimo, problema dei trasporti, problema della ricerca di cammino minimo, problema del flusso di costo minimo, problema del massimo flusso, problema del minimo taglio (50% del corso). 4. Cenni di ottimizzazione lineare intera (ad es. problemi di progettazione di reti, localizzazione di servizi, analisi di dati, instradamento di traffico): metodi esatti (Branch and Bound) e metodi euristici (algoritmi greedy, Tabu Search, Simulated Annealing, Algoritmi Genetici) (5% del corso).
1. Continuous linear optimization: problems and models, simplex method, duality (40% of the course). 2. Analysis of the computational complexity of decision problems (5% of the course). 3. Flows on networks: fundamental concepts of graph theory, finding a spanning tree of minimum cost, transportation problem, shortest path problem, minimum cost flow problem, maximum flow problem, and minimum cut problem (50% of the course). 4. Outline of integer linear optimization (e.g. problems of network design, service location, data analysis, routing): exact methods (Branch and Bound) and heuristics (greedy algorithms, Tabu Search, Simulated Annealing, Genetic Algorithms) (5% of the course).
L’insegnamento integra opportunamente ore di lezione ed ore di esercitazioni, nella misura di circa 60% e 40% del corso, rispettivamente. Le esercitazioni vengono svolte in aula e seguono gli argomenti delle lezioni. Nel laboratorio LADISPE ttp://www.ladispe.polito.it/ sono a disposizione degli studenti i migliori solver di ottimizzazione esistenti sul mercato per risolvere problemi reali, anche di grandi dimensioni. Vengono fornite in aula le istruzioni per il loro uso. Non sono comunque richieste particolari competenze di programmazione.
The course integrates properly teaching hours and hours of practice, to the extent of about 60% and 40% of the course, respectively. The exercises are carried out in the classroom and follow the lecture topics. In the laboratory LADISPE ttp://www.ladispe.polito.it/ up-to-date optimization solvers able to solve real-life problems are available to students. Instructions for their use will be provided in the classroom. No special programming skills are required.
Testi utilizzati per l’insegnamento: R. Tadei, F. Della Croce, Elementi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2010. M. Ghirardi, A. Grosso, G. Perboli, Esercizi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2009. Altro materiale didattico, assieme ad esempi di esami precedenti, è disponibile sul portale della didattica. Testi consigliati per approfondimenti: H. P. Williams, Model building in Mathematical Programming, 4th ed., Wiley, 1999. H. P. Williams, Logic and Integer Programming, Springer, 2009.
Books used for teaching: R. Tadei, F. Della Croce, Elementi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2010. M. Ghirardi, A. Grosso, G. Perboli, Esercizi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2009. Other teaching materials, along with examples of previous exams, is available on the course website. Recommended books for further information: H. P. Williams, Model building in Mathematical Programming, 4th ed., Wiley, 1999. H. P. Williams, Logic and Integer Programming, Springer, 2009.
Modalità di esame: prova scritta;
L’esame è scritto ed è volto ad accertare la conoscenza degli argomenti elencati nel programma del corso e la capacità di applicare le teorie ed i metodi di ottimizzazione visti a lezione alla soluzione degli esercizi proposti. L'esame ha una durata di 2 ore e consiste in una prova scritta con 4 quesiti sugli argomenti contenuti nel programma del corso. L’esame si pone l’obiettivo di verificare le competenze di cui al paragrafo "Risultati dell’apprendimento attesi": l'esame, infatti, comprende una prima domanda, di particolare importanza, che consiste nello scrivere, per un dato problema reale, un corrispondente modello matematico di ottimizzazione lineare che lo rappresenti opportunamente (si veda anche parte 1 del Programma). Le restanti domande sono relative alla complessità computazionale dei problemi decisionali e alla risoluzione di problemi di ottimizzazione su reti visti a lezione (si vedano anche parte 2 e parte 3 del Programma). Durante la prova scritta non si potranno consultare testi, dispense e formulari. Inoltre, non è ammesso portare in aula dispositivi multimediali con accesso al web (ad esempio, smartphone, smartwatch e tablet). L’esame è superato se l’elaborato scritto ottiene un voto da 18/30 a 30/30 (lode inclusa). Verrà utilizzata una scala da 0 a 32 punti per la valutazione. La lode verrà assegnata se la votazione è di 32/30. L’esito della prova sarà comunicato agli studenti tramite un avviso sul portale della didattica. Gli studenti potranno visionare il compito e la relativa valutazione durante un incontro generale la cui data verrà fissata di volta in volta. La data dell’incontro sarà comunicata agli studenti tramite avviso sul portale della didattica in concomitanza con la pubblicazione dei risultati della prova scritta.
Exam: written test;
The exam is written and is aimed to check the knowledge of the topics listed in the program of the course and the ability to apply the optimization theories and methods seen in class to the solution of the proposed exercises. The exam has a duration of 2 hours and consists of a written test with 4 questions on the topics contained in the course program. The exam aims to verify the skills referred to in the paragraph "Expected Learning Outcomes": the exam, in fact, includes a first question, of particular importance, which consists in writing, for a given real problem, a corresponding mathematical model of linear optimization that represents it appropriately (see also part 1 of the Program). The remaining questions are related to the computational complexity of decision-making problems and the resolution of optimization problems on networks seen in class (see also Part 2 and Part 3 of the Program). During the written test it will not be possible to consult texts, lecture notes and forms. Furthermore, multimedia devices with access to the web (for example, smartphones, smartwatches and tablets) are not allowed in the classroom. The exam is passed if the written test gets a vote from 18/30 to 30/30 (including praise). A scale of 0 to 32 points will be used for evaluation. The honors will be awarded if the vote is 32/30. The outcome of the test will be communicated to the students through a notice on the teaching portal. Students can view the task and its assessment during a general meeting whose date will be fixed from time to time. The date of the meeting will be communicated to the students through a notice on the teaching portal in conjunction with the publication of the results of the written test.


© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
m@il