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, 01QNKPM

A.A. 2021/22

2021/22

Ottimizzazione per il problem solving

L'insegnamento 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.

Ottimizzazione per il problem solving

The course Optimization for Problem Solving allows us 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 that is sufficiently representative of the problem itself. Objective function and variables constitute this model, and appropriate constraints to be satisfied. Suitable algorithms and optimization solvers then solve the above model.

Ottimizzazione per il problem solving

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), intera (cioè, dove le variabili sono intere) e di flussi su reti. 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, acquisendo un corretto approccio al problem solving, che potranno proficuamente utilizzare nelle più svariate situazioni decisionali della loro vita.

Ottimizzazione per il problem solving

The 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 also be 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.

Ottimizzazione per il problem solving

Non sono richiesti prerequisiti. Le uniche conoscenze pregresse sono quelle già acquisite nei corsi di base di Ingegneria.

Ottimizzazione per il problem solving

No prerequisites are required. The only prior knowledge is those already acquired in the first-year engineering courses.

Ottimizzazione per il problem solving

1. Ottimizzazione lineare: problemi e modelli. Metodo del simplesso e derivati (25% 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 (35% del corso). 4. Ottimizzazione lineare intera (ad es. problemi di progettazione di reti, localizzazione di servizi, instradamento di traffico, schedulazione): metodi esatti (Branch and Bound) e metodi euristici (ad es. algoritmi Greedy, Metaeuristiche, Ricerca locale, Tabu Search, Algoritmi Genetici) (35% del corso).

Ottimizzazione per il problem solving

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).

Ottimizzazione per il problem solving

Ottimizzazione per il problem solving

Ottimizzazione per il problem solving

L’insegnamento integra opportunamente ore di lezione ed ore di esercitazioni, nella misura di circa 66% e 33% del corso, rispettivamente. Le esercitazioni vengono svolte in aula e seguono gli argomenti delle lezioni. Nel laboratorio LADISPE http://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. In alcuni casi è possibile installarli anche sui PC personali degli studenti. Vengono fornite in aula le istruzioni per il loro uso. Non sono comunque richieste particolari competenze di programmazione.

Ottimizzazione per il problem solving

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 LADISPE laboratory, http://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 specialized programming skills are required.

Ottimizzazione per il problem solving

Testi utilizzati per l’insegnamento: R. Tadei, F. Della Croce, Elementi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2010. R. Tadei, F. Della Croce, A. Grosso, Fondamenti di Ottimizzazione, Progetto Leonardo, Editrice Esculapio, Bologna, 2005. 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. D.G. Luenberger, Y. Ye (2008), Linear and Non Linear Programming, Addison Wesley - https://web.stanford.edu/class/msande310/310trialtext.pdf M. Fischetti (2018), Lezioni di Ricerca Operativa, EAN:9781980835011 R.K. Ahuja et al., Network Flows, Prentice-Hall, New Jersey, 1993.

Ottimizzazione per il problem solving

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.

Ottimizzazione per il problem solving

Modalità di esame: Prova scritta (in aula);

Ottimizzazione per il problem solving

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 1,5 ore e consiste in una prova scritta con diversi 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. Le restanti domande sono relative alla complessità computazionale e ai metodi di risoluzione di problemi di ottimizzazione continui ed interi visti a lezione. 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.

Ottimizzazione per il problem solving

Exam: Written test;

Ottimizzazione per il problem solving

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.

Ottimizzazione per il problem solving

Modalità di esame: Prova scritta a risposta aperta o chiusa tramite PC con l'utilizzo della piattaforma di ateneo Exam integrata con strumenti di proctoring (Respondus);

Ottimizzazione per il problem solving

L’esame si svolge tramite l'ausilio della piattaforma Exam (accessibile dalla propria pagina studente, nella sezione “Esami in remoto”, 30 minuti prima dell’inizio dell’appello a cui si risulta iscritti). Il software Respondus viene utilizzato per garantire l’inibizione di qualsiasi software oltre al browser sul proprio computer. L'esame prevede, analogamente a quello in presenza, una domanda relativa alla modellazione di un problema di ottimizzazione, e una serie di quesiti (a risposta aperta e/o multipla) relativi alla complessità computazionale e ai metodi di risoluzione di problemi di ottimizzazione continui ed interi visti a lezione. Dotazione necessaria: un computer dotato di webcam, microfono, altoparlanti e accesso a internet. Sul PC deve essere installato il programma “Respondus LockDown Browser”. Il PC deve essere collegato alla presa di corrente per tutta la durata della prova. Non è consentito l’uso di qualsiasi altro dispositivo elettronico, accessorio o periferica (es: auricolari, cuffie, smart watch, cellulari, schermi aggiuntivi, ecc.). Non è consentito l’utilizzo e la consultazione di libri, appunti o altro materiale. È tuttavia ammesso l’utilizzo di matite, gomma e righello. È anche possibile avere qualcosa da bere (es. bottiglietta d’acqua). Non è consentito alzarsi o allontanarsi dalla postazione per tutta la durata della prova. L’esame deve essere svolto in un luogo silenzioso e correttamente illuminato della propria abitazione, privo di altre persone per tutta la durata della prova. Viene invalidato il compito a chiunque, per qualsiasi motivo, non rispetti anche una sola delle regole citate o che sia scoperto (anche successivamente tramite l’ausilio delle registrazioni) in comportamenti non conformi ad esse. In base alla gravità dell’infrazione, il docente può decidere se comunicare tale comportamento alle opportune commissioni disciplinari d’Ateneo.

Ottimizzazione per il problem solving

Exam: Computer-based written test with open-ended questions or multiple-choice questions using the Exam platform and proctoring tools (Respondus);

Ottimizzazione per il problem solving

The exam takes place with the help of the Exam platform (accessible from the student page, in the "Esami in remoto" section, 30 minutes before the start of the appeal to which you are enrolled), the Virtual Classroom and the Elaborati section (tab accessible from the main web page of the course). Besides, the Respondus software is used to inhibit any software in addition to the browser on the student computer. The exam program and its structure remain unchanged compared to what is written in the Study Manifesto. Furthermore, due to possible complications introduced by the remote mode, the exam difficulty and length are reduced, so that it can be completed in one hour and a half instead of in two hours, as in previous years. The remaining hour, of the two and a half hours available for the exam, will be devoted to performing Phases I and III (see below). Equipment needed • A computer (hereafter PC) equipped with a webcam, microphone, speakers, and internet access [will mainly serve to view the exam text]. The "Respondus LockDown Browser" program must be installed on the PC. The PC must be connected to the power outlet for the duration of the test. • A mobile device, such as a mobile phone or tablet (henceforth CELL), equipped with a camera and internet access [will be used to interface with the teacher and for the final scan/upload of the homework]. An app for creating pdfs from camera images must be installed on the CELL (CamScanner is recommended). The CELL must be connected to the power outlet for the duration of the test. All on-screen notifications must be disabled (e.g., WhatsApp, Telegram, email messages, etc.). • Pen and enough white sheets. The use of any other electronic device, accessory or peripheral (e.g., earphones, headphones, smartwatches, cell phones, additional screens, etc.) is not allowed. The use and consultation of books, notes, or other materials are not allowed. However, the use of pencils, erasers, and rulers is permitted. It is also possible to have something to drink (e.g., a bottle of water). The exam must be carried out in a quiet and adequately lit place in your home, free of other people for the duration of the test. The CELL must be positioned in such a way that a good and full camera frames the student's torso/face and position (hands and sheets). Furthermore, the CELL must not be reachable by the student when sitting at the desk. We recommend finding the best location in advance. Conduct of the test The conduct of the test, lasting a total of two and a half hours, involves the following steps in sequence. PHASE I - Appeal and checks [maximum 40 min] The student connects to the Virtual Classroom through the CELL within the time indicated for the exam, keeping the webcam and microphone temporarily disabled, and awaits the teacher's instructions. The invitation to the Virtual Classroom will be sent 30 minutes before the exam begins. The student also connects to Exam via PC, where the exam topic will be present (but will not be accessible because it is password protected). The teacher starts the registration and carries out the appeal. The student who, for any reason, will not respond to the appeal within 15 minutes of its start will be considered "absent". The teacher then interacts with each student (who will activate the CELL webcam and microphone). The student will be asked to: • show a valid identification document • show the compliance of the workplace and the surrounding environment • position the CELL and stabilize the frame, which must be maintained for the whole duration of the exam. The CELL is muted, and the student sits at the station, waiting for the start of the test. PHASE II - Examination procedure [1 hour and a half] 1. The teacher orally communicates the password to all those present. 2. The student starts the exam (this involves Respondus blocking the browser) and carries out the test. 3. At the end of the time, notified by the teacher, all students immediately stop writing. The student who finishes first must still wait for the deadline. PHASE III - Loading the homework [maximum 20 min] 1. Upon instruction from the teacher, students stop the browser block (Respondus) on the PC and the audio/video streaming on Virtual Classroom from the CELL and access the Virtual Classroom via PC (with webcam and audio-activated). 2. Through the CELL, the student scans his/her assignment and uploads it to the portal in the appropriate "Elaborati" section (see the upload and format of the assignment). Students are advised to recheck by downloading it to the PC from the "Elaborati" section, that the uploaded file is readable, correct, and complete. If not, delete the old version and upload a new one. 3. The student, satisfied with its uploading, communicates it to the teacher. The teacher makes sure of the delivery and talks to the student that he/she is free to leave the Virtual Classroom, ending the exam. Students, who for any reason, have not been able to upload their assignment will be considered "withdrawn". Only the parts of the homework delivered will be evaluated. Uploads/cancellations of assignments after the end of the exam will not be evaluated. Other important clarifications Homework upload and format Each sheet of the assignment must include the student's family name, name, and registration number. The student must upload ONE SINGLE FILE, in pdf format and named "FamilynameName.pdf", obtained by aggregating the photographs of the different sheets through a particular app (e.g., CamScanner). The behavior to be maintained for the duration of the test • the audio/video streaming both in and out of the CELL must be active; • it is not possible to get up or move away from the position; • it is not possible to contact/communicate with other people outside the teacher; • no one must enter the student's room; • it is not possible to use the CELL except during the initial control or final loading phases of the homework, and only for those operations; • it is not possible to eat. Maximum silence is recommended so as not to disturb other students. Anyone wishing to ask a question during the test can do so by specifying their family name and name first. Withdrawals A student can withdraw from the exam at any time. In that case, however, the student must have the following behavior: • communicate their decision to the teacher, who will notify the withdrawal. This decision will be permanent; • must remain connected to the Virtual Classroom and comply with the above rules until the end of Phase II. At that point, the student must not upload any files and can abandon the Virtual Classroom. Infringements The exam is invalidated for anyone, for any reason, who does not comply with even one of the rules above or who is discovered (even later with the aid of the registrations) in behaviors that do not comply with them. If these violations occur during the test, students must withdraw at the request of the teacher, and they must behave as in "Withdrawals". Based on the gravity of the infringement, the teacher may decide whether to communicate this behavior to the appropriate University disciplinary commissions. Special Needs Students who request Special Needs will have 30% more time (therefore, half an hour more) available for the test. In any case, at the end of PHASE II, those students will also temporarily stop writing, so that the teacher can devote himself to the delivery by the other students, and they are not disturbed by these operations. Once the delivery is over, and silence returns, those students can resume their test. Emergencies For any emergency during the exam, students can call the following mobile numbers: Prof. Roberto Tadei 335 6604376 Prof. Daniele Manerba 339 5454453. Honor code At least 48 hours before the start of the exam and not earlier than 7 days from the day of the exam, students enrolled in the exam must upload a file in pdf format on the course portal under "Elaborati", called "SurnameName_codeofhonour.pdf" , containing the form "CODE-OF-HONOR-STATEMENT ON WRITTEN & ORAL EXAMS IN REMOTE MODE", duly completed and signed. Students who do not upload the file within the scheduled time cannot take the exam. Rating As usual, students will receive notification of the test result via the portal. At the same time, the date and time of the vision of the homework will be communicated, which will take place through Virtual Classroom. The registration of the exam will immediately follow the vision of the homework. Students, who wish to reject their mark, even after viewing the assignment, must communicate it by email to Prof. Tadei (roberto.tadei@polito.it) by the date of registration.

Ottimizzazione per il problem solving

Modalità di esame: Prova scritta (in aula); Prova scritta a risposta aperta o chiusa tramite PC con l'utilizzo della piattaforma di ateneo Exam integrata con strumenti di proctoring (Respondus);

Ottimizzazione per il problem solving

Esame da remoto: Si veda "Criteri, regole e procedure per l'esame in remoto". Esame in presenza: Come per l'esame da remoto, ma in questo caso l'esame scritto viene sostenuto in classe invece che da remoto.

Ottimizzazione per il problem solving

Exam: Written test; Computer-based written test with open-ended questions or multiple-choice questions using the Exam platform and proctoring tools (Respondus);

Ottimizzazione per il problem solving

Online exam: See "Assessment and grading criteria for online exam". Onsite exam: As for the online exam, where the exam test is done in the classroom instead of online.

Esporta Word


© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
Contatti