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 093735 - GRAPH OPTIMIZATION
Docente Carello Giuliana
Cfu 5.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 (263) MUSIC AND ACOUSTIC ENGINEERING*AZZZZ093735 - GRAPH OPTIMIZATION
Ing Ind - Inf (Mag.)(ord. 270) - MI (474) TELECOMMUNICATION ENGINEERING - INGEGNERIA DELLE TELECOMUNICAZIONI*AZZZZ093735 - GRAPH OPTIMIZATION
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA*AZZZZ093735 - GRAPH OPTIMIZATION
Ing Ind - Inf (Mag.)(ord. 270) - MI (487) MATHEMATICAL ENGINEERING - INGEGNERIA MATEMATICA*AZZZZ093735 - GRAPH OPTIMIZATION

Obiettivi dell'insegnamento

The course deals with some important network and graph optimization problems arising in several fields of application such as telecommunication, transportation and logistics. The course presents the optimization models for the different classes of problems and describes the main methods that have been proposed to tackle them.

The aim of the course is to provide students with a classification of optimization problems related to networks and other applications. Further, the course aims at providing the students with the knowledge of a wide range of optimization methods. The students will learn to model optimization problems arising in real life applications, to represent them as particular case of well known optimization problems, and to deal with them applying both exact and heuristic approaches. Beside theoretical knowledge, the course will provide practical experience in developing and applying the optimization techniques. During lab sessions, the students will be asked to apply their knowledge to deal with problems.


Risultati di apprendimento attesi

The student will know

- some of the main families of optimization problems (network design and flows, location, scheduling)

- the main heuristic methods, their features and properties

- the main relaxation approaches

- the valid inequalities and some classical examples

 

The student will be able to use his/her knowledge to tackle an optimization problem, i.e. the student will be able to

- identify the mathematical model underlaying an application problem

- design a heuristic approach to tackle a problem, implement it  and evaluate its performance

- apply relaxation techniques and implement them to obtain a bound for a problem

- derive valid inequalities based on classical examples and implement them to improve the bound

 

 


Argomenti trattati

Introduction. Brief review of mathematical programming models for graph and network optimization problems (paths, trees, minimum cost flow, maximum flow, travelling salesman problem, knapsack problem). Brief review of the Branch-and-Bound method and basic Cutting Plane method (Gomory cuts). 

Flow routing and Fixed Charge Network Design problems. Classification: splittable vs unsplittable flow, single vs multiple paths, multicommodity flows, node and arc fixed costs. Arc-based and path-based ILP models.

Column generation method. Dual problem and complementary conditions, the pricing problem.

Heuristic methods.  Greedy algorithm.  Local Search. Metaheuristics: tabu search, simulated annealing, variable neighborhood search. Very large scale neighborhood and ILP based neighborhood. Examples of application of heuristic methods.

Location problems. Classification: set covering and set partitioning, p-center and p-median problems, uncapacitated and capacitated facility location problems, single assignment and multiple assignment.

Valid inequalities and cutting planes.  Cover inequalities for knpasack problem. Valid inequalities for network design and connectivity requirements.

Relaxation. Continuous relaxation, surrogate relaxation. Lagrangian relaxation: general framework and  application to facility location problems and network design problems.

Scheduling problems. Introduction to scheduling problems. Classification: single machine scheduling with different objective functions (total weighted completion time, makespan, lateness, tardiness), parallel machines scheduling problems, flow shop, job shop. Models and algorithms for scheduling problems.

 

 


Prerequisiti

Basic knowledge of linear programming and simplex method are required


Modalità di valutazione

The exam includes a written test and a lab exam.

The written test includes:

- exercises: the student is required to apply the knowledge for solving small examples and for applying the optimization methods to a given problem

- theoretical questions on course topics with open answer: the student is required to demonstrate his/her knowledge of the optimization methods

The lab part includes homeworks: the student is required to apply the methods and implement them to solve problems


Bibliografia
Risorsa bibliografica facoltativaR. Ahuja, T. Magnanti, J. Orlin, Network flows: Theory, Algorithms, and Applications, Editore: Prentice Hall, Anno edizione: 1993
Risorsa bibliografica facoltativaD. Bertsekas, Network Optimization: Continuous and Discrete Models, Editore: Athena Scientific, Anno edizione: 1998
Risorsa bibliografica facoltativaF.W.Glover, G.A.Kochenberger, Handbook of Metaheuristics, Editore: Springer-Verlag, Anno edizione: 2003
Risorsa bibliografica facoltativaH.W. Hamacher, Z. Drezner, Facility Location: Applications and Theory, Editore: Springer, Anno edizione: 2001
Risorsa bibliografica facoltativaB. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms, Editore: Springer Verlag, Anno edizione: 2001
Risorsa bibliografica facoltativaL. Wolsey, Integer Programming, Editore: Wiley, Anno edizione: 1998
Risorsa bibliografica facoltativaM.L. Pinedo, Scheduling - Theory, Algorithms, and Systems, Editore: Springer, Anno edizione: 2008
Risorsa bibliografica facoltativaV.J. Rayward-Smith, I.H. Osman, C.R. Reeves, G.D. Smith, Modern heuristic search methods, Editore: Wiley and Sons, Anno edizione: 1996
Risorsa bibliografica facoltativaM. Piòro, D. Medhi, Routing, Flow, and Capacity Design in Communica- tion and Computer Networls, Editore: Elsevier, Anno edizione: 2004
Risorsa bibliografica facoltativaS.Martello, P.Toth, Knapsack problems, Editore: Wiley, Anno edizione: 1990

Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
26:00
39:00
Esercitazione
12:00
18:00
Laboratorio Informatico
18:00
12:00
Laboratorio Sperimentale
0:00
0:00
Laboratorio Di Progetto
0:00
0:00
Totale 56:00 69: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
schedaincarico v. 1.6.1 / 1.6.1
Area Servizi ICT
18/02/2020