Guida degli insegnamenti
Syllabus
Partially translatedTradotto parzialmente
Fabrizio MARINELLI
Lingua di erogazione: ITALIANOLessons taught in: ITALIAN
Laurea Magistrale - [IM12] INGEGNERIA INFORMATICA E DELL'AUTOMAZIONE Master Degree (2 years) - [IM12] COMPUTER AND AUTOMATION ENGINEERING
Dipartimento: [040040] Dipartimento Ingegneria dell'InformazioneDepartment: [040040] Dipartimento Ingegneria dell'Informazione
Anno di corsoDegree programme year : 1 - Primo Semestre
Anno offertaAcademic year: 2019-2020
Anno regolamentoAnno regolamento: 2019-2020
Obbligatorio
Crediti: 6
Ore di lezioneTeaching hours: 48
TipologiaType: C - Affine/Integrativa
Settore disciplinareAcademic discipline: MAT/09 - RICERCA OPERATIVA
Italiana
Italian
Elementi di programmazione lineare e di teoria della dualità. Concetti elementari di programmazione strutturata.
Elements of Linear Programming and duality theory. Elements of structured programming.
48 ore di lezioni frontali
48 hours of frontal lessons
Il corso mira all'acquisizione degli strumenti avanzati delle tecniche di ottimizzazione discreta: teoria dei grafi e metodi di ottimizzazione su rete, programmazione lineare intera e ottimizzazione combinatoria, nonché la conoscenza del linguaggio di modellazione AMPL e dei principali software di ottimizzazione.
Capacità di applicare conoscenze e comprensione.
Lo studente sarà in grado di individuare i metodi e gli algoritmi più appropriati per la risoluzione di problemi decisionali e di ottimizzazione discreta, nonché di progettare e implementare algoritmi di ottimizzazione esatti ed euristici.
Competenze trasversali.
La prova scritta e la discussione orale sulle proprietà teoriche dei metodi di ottimizzazione discreta descritti nel corso e sulle applicazioni di tali metodi a problemi di decisioni consentirà di migliorare le abilità comunicative e la capacità di apprendimento in autonomia dello studente. L'autonomia di giudizio verrà potenziata dalla necessità di individuare le tecniche più appropriate per ogni contesto applicativo.
Knowledge and Understanding.
The course aims at the acquisition of advanced tools of discrete optimization techniques: graph theory and optimization methods on networks, integer linear programming and combinatorial optimization, as well as the knowledge of the modeling language AMPL and of the main optimization software.
Capacity to apply Knowledge and Understanding.
The student will be able to identify the most appropriate methods and algorithms for solving decision and discrete optimization problems, as well as designing and implementing exact and heuristic optimization algorithms.
Transversal Skills.
The written exam and the oral discussion about the theoretic properties of the discrete optimization methods described in the course as well as the applications of such methods to decision-making problems will help to improve the student communication skills and the ability to learn independently. The judgement skill will be enhanced by the need to identify the most appropriate techniques for each application context.
- La programmazione matematica come paradigma dichiarativo.
- Modelli di programmazione lineare (PL) e lineare intera (PLI).
- Tecniche di modellazione per la PL/PLI.
- Software di ottimizzazione e linguaggi di modellazione algebrica (AMPL).
- Richiami di programmazione lineare e teoria della dualità: risultati principali e applicazioni.
- Cenni di teoria della complessità computazionale.
- Introduzione alla teoria dei grafi e principali problemi di ottimizzazione su grafo.
- Problemi modelli e algoritmi di ottimizzazione su reti: minimo albero ricoprente, cammino minimo, massimo flusso e flusso a costo minimo.
- Algoritmo dei piani di taglio. Tagli di Gomory e disuguaglianze Cover per zaino 0-1.
- Algoritmi di enumerazione implicita per la PLI.
- Applicazioni della programmazione matematica.
- Mathematical programming as a declarative paradigm.
- Linear programming (LP) and integer linear programming (ILP) models.
- Modelling techniques for LP/ILP.
- Software optimization tools and Algebraic Modelling Languages (AMPL).
- Outline on linear programming and duality theory: main results and applications.
- Primer to theory of computational complexity.
- Introduction to graph theory and main graph optimization problems.
- Problems, models and algorithms for network optimization: minimum spanning tree, shortest path, max-flow and min cost flow problems.
- The method of cutting planes. Gomory cuts and cover inequalities for Knapsack 0-1
- Implicit enumeration algorithms for Integer Linear Programming.
- Applications of mathematical programming.
La valutazione del livello di apprendimento prevede una prova scritta e una prova orale. La prova scritta, della durata di 2 ore, è articolata in una prima parte con domande a risposta chiusa e una seconda parte con uno o più esercizi di modellazione matematica e/o di soluzione di problemi di ottimizzazione discreta mediante le tecniche presentate nel corso. La prova scritta non prevede la possibilità di utilizzare testi o appunti. Alla prova orale accede chi ha ottenuto una valutazione dello scritto di almeno 18 punti. La prova orale consiste nella discussione dello scritto e nella soluzione di uno o più quesiti volti a verificare le capacità logiche deduttive e l'apprendimento degli argomenti dell’insegnamento.
Criteri di valutazione dell'apprendimento.
Viene valutata la capacità di sintetizzare ed esporre con chiarezza e rigore logico idee, concetti e risultati teorici dell'ottimizzazione discreta. Viene inoltre valutata la capacità di impostare e risolvere autonomamente i problemi decisionali utilizzando in modo corretto e pertinente metodologie, modelli e strumenti propri della programmazione matematica e dell'ottimizzazione discreta.
Criteri di misurazione dell'apprendimento.
La conoscenza dei concetti e dei risultati teorici è misurata analiticamente con un punteggio assegnato alla prima parte della prova scritta compreso tra -7 e 14. La capacità di impostare e risolvere problemi decisionali con strumenti propri della programmazione matematica e dell'ottimizzazione discreta è misurata analiticamente con un punteggio assegnato alla seconda parte della prova scritta compreso tra 0 e 14. La capacità di sintesi, di rigore logico e di esposizione chiara è misurata analiticamente con un punteggio assegnato alla prova orale compreso tra 0 e 30.
Criteri di attribuzione del voto finale.
Il voto finale è pari alla semisomma dei punteggi assegnati alle due parti della prova scritta e alla prova orale. La votazione massima, pari a trenta punti con lode, è assegnata agli studenti che complessivamente dimostrino completa padronanza degli strumenti teorici e metodologici propri dell'ottimizzazione discreta e piena autonomia e rigore logico nell'impostare e risolvere i problemi posti.
La votazione minima, pari a diciotto, è assegnata agli studenti che dimostrino di riuscire a risolvere i problemi posti e di avere sufficiente conoscenza degli strumenti teorici e metodologici propri dell'ottimizzazione discreta.
Learning Evaluation Methods.
The assessment of the level of learning includes both a written and an oral exam. The written lasts 2 hours and is composed by a first part with multiple-choice tests and a second part with one or more exercises on mathematical modeling and/or solution of discrete optimization problems by means of the techniques presented in the course. During the exam students cannot use notes and books. The access to the oral exam is reserved to students that achieve a written rating of at least 18 points. The oral exam consists of the discussion of the written exam and the solution of one or more questions in order to verify the logical deductive skills and the understanding of the course topics.
Learning Evaluation Criteria.
It is evaluated the ability to clearly and logically explain ideas, concepts and theoretical results of discrete optimization. It is also assessed the ability to independently set and solve decision problems by correctly using appropriate methods, models and tools of mathematical programming and discrete optimization.
Learning Measurement Criteria.
Knowledge of ideas, concepts and theoretical results is analytically measured by a score assigned to the first part of the written exam that ranges between -7 and 14 points. The ability to formulate and solve decision-making problems by means of the tools of mathematical programming and discrete optimization is analytically measured by a score assigned to the second part of the written that ranges between 0 and 14 points. the capability of synthesis, logical and clear exposition is measured analytically by a score assigned to the oral exam that ranges between 0 and 30 points.
Final Mark Allocation Criteria.
The final grade is equal to the half-sum of the scores awarded to the two parts of the written exam and to the oral exam. The maximum grade, equal to thirty points with honors, is awarded to students who demonstrate total mastery of the theoretical and methodological tools of discrete optimization, and full autonomy and logical accuracy in setting and solving the proposed problems.
The minimum grade, equal to eighteen, is assigned to students who demonstrate to be able to solve the proposed problems and to sufficiently know of the theoretical and methodological tools of discrete optimization.
1) C. Vercellis, "Ottimizzazione. teoria, metodi, applicazioni", Mc Graw-Hill, 2008.
2) appunti, esercizi e slide delle lezioni disponibili sulla piattaforma e-learning di Ateneo alla pagina https://learn.univpm.it.
1) C. Vercellis, "Ottimizzazione. Teoria, metodi, applicazioni", Mc Graw-Hill, 2008.
2) presentations, exercises and lecture notes available on the e-learning platform at page https://learn.univpm.it.
No
No
Le informazioni contenute nella presente scheda assumono carattere definitivo solo a partire dall'A.A. di effettiva erogazione dell'insegnamento. Academic year 2019-2020
Università Politecnica delle Marche
P.zza Roma 22, 60121 Ancona
Tel (+39) 071.220.1, Fax (+39) 071.220.2324
P.I. 00382520427