Risorse bibliografiche
 Risorsa bibliografica obbligatoria Risorsa bibliografica facoltativa
 Scheda Riassuntiva
 Anno Accademico 2015/2016 Scuola Scuola di Ingegneria Industriale e dell'Informazione Insegnamento 095972 - OPTIMIZATION Cfu 8.00 Tipo insegnamento Monodisciplinare Docenti: Titolare (Co-titolari) Amaldi Edoardo

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
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, choice of Lagrangian dual.  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.
- Line search methods and convergence rate.
- One-dimensional optimization (Wolfe conditions).
- 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. The prerequisite to take the written exam is that the students must have attended and actively participated in at least 5 of the 6 computer laboratory sessions.

 Bibliografia
 Slides of the lectures, material for the exercise and computer laboratory sessions http://home.deib.polimi.it/amaldi/OPT-15-16.shtmlNote:The material will be made available during the semester M. S. Bazaraa, H. D. Sherali, C. M. Shetty, Nonlinear programming: Theory and Algorithms, Third edition, Editore: Wiley­Interscience, Anno edizione: 2006 J. Nocedal, S. Wright, Numerical optimization, First edition, Editore: Springer, Anno edizione: 1999 L. A. Wolsey, Integer Programming, Editore: J. Wiley & Sons, Anno edizione: 1998 D. Bertsekas, Nonlinear programming,  Second edition, Editore: Athena Scientific, Anno edizione: 2003 S. Boyd, L. Vandenberghe, Convex optimization, Editore: Cambridge Univeristy Press, Anno edizione: 2004 http://www.stanford.edu/~boyd/cvxbook/ D. G. Luenberger, Y. Ye, Linear and nonlinear programming, Editore: Springer Science+Business Media, Anno edizione: 2008Note:Third edition M. Minoux, Mathematical programming: Theory and algorithms, Editore: John Wiley and Sons, Anno edizione: 1986 A. Ruszczynski, Nonlinear optimization, Editore: Princeton University Press, Anno edizione: 2006

 Software utilizzato
 Nessun software richiesto

 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.9.6 / 1.9.6 Area Servizi ICT 22/05/2024