logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2014/2015
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 095972 - OPTIMIZATION
Docente Amaldi Edoardo
Cfu 8.00 Tipo insegnamento Monodisciplinare

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (Mag.)(ord. 270) - MI (403) INGEGNERIA MATEMATICA* AZZZZ095972 - OPTIMIZATION
Ing Ind - Inf (Mag.)(ord. 270) - MI (434) INGEGNERIA INFORMATICA* AZZZZ089076 - COMPLEMENTI DI RICERCA OPERATIVA
089187 - OTTIMIZZAZIONE DISCRETA
Ing Ind - Inf (Mag.)(ord. 270) - MI (436) INGEGNERIA DELL'AUTOMAZIONE* AZZZZ089187 - OTTIMIZZAZIONE DISCRETA
089076 - COMPLEMENTI DI RICERCA OPERATIVA
Ing Ind - Inf (Mag.)(ord. 270) - MI (473) AUTOMATION AND CONTROL ENGINEERING - INGEGNERIA DELL'AUTOMAZIONE* AZZZZ089076 - COMPLEMENTI DI RICERCA OPERATIVA
089187 - OTTIMIZZAZIONE DISCRETA
Ing Ind - Inf (Mag.)(ord. 270) - MI (474) TELECOMMUNICATION ENGINEERING - INGEGNERIA DELLE TELECOMUNICAZIONI* AZZZZ089076 - COMPLEMENTI DI RICERCA OPERATIVA
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA* AZZZZ089187 - OTTIMIZZAZIONE DISCRETA
089076 - COMPLEMENTI DI RICERCA OPERATIVA
Ing Ind - Inf (Mag.)(ord. 270) - MI (487) MATHEMATICAL ENGINEERING - INGEGNERIA MATEMATICA* AZZZZ095972 - OPTIMIZATION

Programma dettagliato e risultati di apprendimento attesi

Aim

 

The purpose of the course is to present the main concepts and methods of discrete optimization and nonlinear (continuous) optimization, which allow to tackle a wide variety of decision-making problems arising in science, engineering and management. Modeling and application-related aspects are also covered.

After some fundamentals of convex analysis, the course is subdivided into two parts. The first one deals with integer linear programming, that is optimization problems with a linear objective function and linear constraints where some (or all) variables are restricted to take discrete (integer) values. The second part is devoted to nonlinear optimization with continuous variables.

During the computer laboratory sessions, the students will learn how to use the softwares AMPL (with state-of-the-art solvers like CPLEX) and MATLAB to build optimization models and solve mixed integer linear and nonlinear optimization problems.

 

Detailed program

 

1. Introduction

 

Discrete (integer) and nonlinear (continuous) optimization models, local and global optima, some fields of application.

2. Fundamentals of convex analysis

 

Separating/supporting hyperplanes, main consequences (Farkas Lemma), characterization of convex functions, subgradients.

3. Discrete optimization


- Integer linear programming (ILP) problems and modeling techniques. Examples: matching, location, routing, scheduling, network flows, covering, packing, partitioning,...
- Alternative, strong and ideal formulations.
- "Easy" ILP problems and totally unimodular matrices.
- Linear, surrogate and combinatorial relaxations.
- Lagrangian relaxation: Lagrangian subproblem, dual problem, subgradient method. Examples: symmetric travelling salesman, facility location and generalized assignment problems.
- Branch-and-Bound method (ILP and combinatorial optimization problems).
- Cutting plane methods: valid inequalities, Chvátal-Gomory procedure, fractional and mixed integer Gomory cuts, facets of polyhedra, strong inequalities (cover inequalities for the binary knapsack problem, clique and odd cycle inequalities for the independent set problem, cut-set inequalities for TSP), separation problem and lifting procedure.
- Branch-and-Cut method.
- Heuristics: greedy, local search and Lagrangian heuristics.

4. Unconstrained nonlinear optimization


- Optimality conditions.
- Convergence rates of iterative methods.
- One-dimensional optimization.
- Line search methods: gradient, conjugate directions, Newton and quasi-Newton methods (DFP and BFGS).
- Subgradient method for convex non-smooth optimization functions.

5. Constrained nonlinear optimization


- Necessary optimality conditions: constraint qualification, Karush-Kuhn-Tucker conditions.
- Sufficient optimality conditions: Lagrange function, saddle points, weak and strong duality.
- Methods for quaratic programming problems (null space and active set methods).
- Penalty, barrier and augmented Lagrangian methods.
- Basics of quadratic sequential programming.

 

Prerequisites

 

The prerequisites for the course include linear programming (basic feasible solutions, simplex algorithm, duality), graph optimization (minimum spanning tree, shortest paths, maximum flow), and the basics of NP-completeness theory. These topics are covered in the course "Foundations of Operations Research".

 

Organization

 

Besides the lectures, the course includes 9 exercise sessions of 90 minutes and 6 computer laboratory sessions of 90 minutes.

Approximately every ten days, the students will be assigned a set of exercises to be solved before the next exercise session.
 

Joint courses: "Ottimizzazione Discreta" and "Complementi di  Ricerca Operativa"

 

The courses "Ottimizzazione Discreta" and "Complementi di Ricerca Operativa" (5 cfu) correpond to two overlapping parts of the course "Optimization" (8 cfu).

While "Optimization" includes all the material presented during the lectures, the exercise and computer laboratory sessions,

- the course "Ottimizzazione Discreta" (5 cfu) includes the chapters 1-3, the exercise series 1-5 and the computer laboratory sessions 1-3,

- the course "Complementi di R.O." (5 cfu) includes the chapters 1, 2, 4 e 5, the exercise series 1,6-9 and the computer laboratory sessions 4-6.

The students enrolled in both courses "Ottimizzazione Discreta" (5 cfu) and "Complementi di R.O." (5 cfu) must take the written exam of "Optimization" (8 cfu) and conduct a project or an individual study (2 cfu) to be defined with the instructor.

 


Note Sulla Modalità di valutazione

A comprehensive written exam covering all the material presented during the lectures, the exercise sessions and the computer laboratory sessions.


Bibliografia
Risorsa bibliografica obbligatoriaSlides of the lectures, material for the exercise and computer laboratory sessions http://home.deib.polimi.it/amaldi/OPT-14-15.shtml
Note:

The material will be made available during the semester

Risorsa bibliografica facoltativaM. S. Bazaraa, H. D. Sherali, C. M. Shetty, Nonlinear programming: Theory and Algorithms, Third edition, Editore: Wiley­Interscience, Anno edizione: 2006
Risorsa bibliografica facoltativaJ. Nocedal, S. Wright, Numerical optimization, First edition, Editore: Springer, Anno edizione: 1999
Risorsa bibliografica facoltativaL. A. Wolsey, Integer Programming, Editore: J. Wiley & Sons, Anno edizione: 1998
Risorsa bibliografica facoltativaD. Bertsekas, Nonlinear programming,  Second edition, Editore: Athena Scientific, Anno edizione: 2003
Risorsa bibliografica facoltativaS. Boyd, L. Vandenberghe, Convex optimization, Editore: Cambridge Univeristy Press, Anno edizione: 2004 http://www.stanford.edu/~boyd/cvxbook/
Risorsa bibliografica facoltativaD. G. Luenberger, Y. Ye, Linear and nonlinear programming, Editore: Springer Science+Business Media, Anno edizione: 2008
Note:

Third edition

Risorsa bibliografica facoltativaM. Minoux, Mathematical programming: Theory and algorithms, Editore: John Wiley and Sons, Anno edizione: 1986
Risorsa bibliografica facoltativaA. Ruszczynski, Nonlinear optimization, Editore: Princeton University Press, Anno edizione: 2006

Mix Forme Didattiche
Tipo Forma Didattica Ore didattiche
lezione
54.0
esercitazione
30.0
laboratorio informatico
0.0
laboratorio sperimentale
0.0
progetto
0.0
laboratorio di progetto
0.0

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.6.1 / 1.6.1
Area Servizi ICT
20/11/2019