logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2018/2019
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 093595 - ADVANCED MATHEMATICAL METHODS (C.I.)
  • 093594 - NUMERICAL METHODS FOR OPTIMIZATION
Docente Novellani Stefano
Cfu 5.00 Tipo insegnamento Modulo Di Corso Strutturato

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (Mag.)(ord. 270) - BV (477) ENERGY ENGINEERING - INGEGNERIA ENERGETICA*AZZZZ093595 - ADVANCED MATHEMATICAL METHODS (C.I.)

Obiettivi dell'insegnamento

The course offers an introduction to linear and discrete optimization. It covers the use of mathematical programming as a means to solve real-world decision-making problems. The course is centered upon presenting optimization models and solution algorithms that fit a wide a variety of applications in engineering, with special attention towards energy applications. The course is accompanied by computer laboratory sessions, which use AMPL modeling language and state-of-the art commercial solvers to tackle optimization problems arising in a variety of fields of application.


Risultati di apprendimento attesi

Students will be able to model real-world decision-making problems with linear and discrete mathematical programming models, with a particular interest to energetic ones. The course will provide the students all the necessary modelling techniques. Students will learn the AMPL modelling language, and will thus be able to solve the modelled problems whit commercial solvers. Thanks to this course, students will also be able to use exact algorithms for both linear and discrete problems, and will have some basic knowledge on heuristic algorithms. Moreover, the course will teach the students how to consider the most important problems defined on graphs and networks and to select the correct algortihm to solve them.

 


Argomenti trattati

1. Introduction

Presenting applications of linear and discrete optimization. Introducing the steps required for formulating optimization problems (decision variables, objective function, constraints). Modeling techniques for Linear Programming and Integer Linear Programming.

2. Graph and network optimization

Optimum spanning trees. Maximum flows: Ford-Fulkerson algorithm and maximum flow-minimum cut theorem. Minimum cost flows.

3. Linear Programming (LP)

LP models. Geometric aspects (vertices of the feasible region) and algebraic aspects (basic feasible solutions). Fundamental properties of linear programming. The Simplex method. LP duality theory: pair of dual problems, weak and strong duality, complementary slackness conditions. Economic interpretation. Sensitivity analysis. Special cases: assignment and transportation problems.

4. Integer Linear Programming (ILP)

ILP models for, among others, scheduling and production planning problems. Relaxation: linear, combinatorial and Lagrangian. Exact methods: Branch & Bound algorithm and cutting plane methods.

5. Heuristics

Local search techniques, metaheuristics applied to scheduling problems and production planning problems. Tabu search.

 


Prerequisiti
 

Modalità di valutazione

The course is held with ex cathedra lessons and hands-on training.


The final evaluation of learning will be obtained through a written test, composed by numerical problems on the main topics of the course. No mid-term tests will take place.

The test evaluates the student's ability for modelling real-world decision making problems, and their ability to translate them into AMPL modelling language. The test will evaluate the student's knowledge on exact algorihtms for solving linear and discrete problems and their ability of chosign the correct algorithm for specific problems, with a particular attention to problems on graphs and networks.


Bibliografia
Risorsa bibliografica facoltativaF. Hillier, G.J. Lieberman, Introduction to Operations Research, Editore: McGraw-Hill, Anno edizione: 2010
Risorsa bibliografica facoltativaR.K. Ahuja, T.L. Magnanti, J.B. Orlin,, Network flows. Theory, algorithms and applications, Editore: Prentice Hall, Anno edizione: 1993
Risorsa bibliografica facoltativaL.A. Wolsey, Integer Programming, Editore: Wiley, Anno edizione: 1998

Software utilizzato
Nessun software richiesto

Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
32:30
48:45
Esercitazione
17:30
26:15
Laboratorio Informatico
0:00
0:00
Laboratorio Sperimentale
0:00
0:00
Laboratorio Di Progetto
0:00
0:00
Totale 50:00 75:00

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Inglese
Disponibilità di materiale didattico/slides in lingua inglese
Disponibilità di libri di testo/bibliografia in lingua inglese
Possibilità di sostenere l'esame in lingua inglese
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.8.0 / 1.8.0
Area Servizi ICT
05/12/2022