Risorse bibliografiche
 Risorsa bibliografica obbligatoria Risorsa bibliografica facoltativa
 Scheda Riassuntiva
 Anno Accademico 2015/2016 Scuola Scuola di Ingegneria Industriale e dell'Informazione Insegnamento 088983 - FOUNDATIONS OF OPERATIONS RESEARCH Cfu 5.00 Tipo insegnamento Monodisciplinare Docente Amaldi Edoardo

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (Mag.)(ord. 270) - MI (474) TELECOMMUNICATION ENGINEERING - INGEGNERIA DELLE TELECOMUNICAZIONI*MZZZZ096108 - NETWORK DESIGN
088983 - FOUNDATIONS OF OPERATIONS RESEARCH
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA*MZZZZ088983 - FOUNDATIONS OF OPERATIONS RESEARCH

 Programma dettagliato e risultati di apprendimento attesi
 AimOperations Research (O.R.) is the branch of applied mathematics dealing with quantitative methods to analyze and solve complex real-world decision-making problems. The course covers some of the fundamental methods of O.R. The focus is on optimization models and algorithms with important applications in computer science, telecommunications and engineering. During the computer laboratory sessions the students will learn to use the AMPL modeling language and state-of-the-art commercial solvers to tackle optimization problems arising in a variety of fields of application. Detailed program1. IntroductionDecision-making problems. Main steps of an O.R. study. Different types of optimization (mathematical programming) problems. Optimization models (decision variables, objective function, constraints) and modeling techniques.2. Graph and network optimizationAlgorithms for the optimum spanning tree and shortest path problems (including Dynamic programming for acyclic graphs). Application to project scheduling: critial path method and Gantt diagrams. Maximum flows: Ford-Fulkerson algorithm and maximum flow-minimum cut theorem. Minimum cost flows, matching in bipartite graphs.  3. Basics of computational complexityRecognition problems, classes P and NP, NP-complete and NP-hard problems. Traveling salesman problem, Integer Linear Programming and other examples.4. 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.5. Integer Linear Programming (ILP)ILP models for, among others, routing, scheduling and location problems. Formulations and linear relaxation. Exact methods: Branch & Bound algorithm and relaxations, cutting plane method with fractional Gomory cuts. Time permitting: introduction to heuristic algorithms (greedy and local search).

 Note Sulla Modalità di valutazione
 The examination consists of a written exam and an optional computer laboratory exam.The written exam, which covers all the material presented in the lectures, exercise and computer laboratory sessions, includes several problems to be solved in class during the allotted time. The maximum grade is 27.In the computer laboratory exam, the students wil build the optimization model for an assigned decision-making problem and solve it with the modeling language and optimization solver used in the laboratory sessions (AMPL and CPLEX). The computer laboratory exam is optional and the maximum grade is 4. The computer lab exam will be scheduled on a specific date at the end of the semester.The final grade is obtained by adding the grades of the written exam and of the computer laboratory exam (if any).

 Bibliografia
 Lecture notes and slides (English and Italian) http://home.deib.polimi.it/malucell/didattica/appunti/materiale.html Slides of the lectures, material for the exercise and computer laboratory sessions, past exam questions http://home.deib.polimi.it/amaldi/FOR-15-16.htmlNote:The material will be made available progressively during the semester Exercises from past exams (English and Italian) http://home.deib.polimi.it/malucell/didattica/esercizi/esercizi.html R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network flows. Theory, algorithms and applications, Editore: Prentice Hall, Anno edizione: 1993 D. Bertsimas, J. Tsitsiklis, Introduction to linear optimization, Editore: Athena Scientific, Anno edizione: 1997 F. Hillier, G.J. Lieberman, Introduction to Operations Research, Editore: Ninth edition, McGraw-Hill, Anno edizione: 2010 C.H. Papadimitrou, K. Steiglitz, Combinatorial optimization: Algorithms and complexity, Editore: Dover, 1998, Anno edizione: 1998Note:First edition: Prentice Hall, 1982

 Software utilizzato
 Nessun software richiesto

 Mix Forme Didattiche
Tipo Forma Didattica Ore didattiche
lezione
35.0
esercitazione
15.0
laboratorio informatico
10.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.1 / 1.9.1 Area Servizi ICT 23/04/2024