Contents


Network optimization: shortest path, maximum flow and minimum cost flow problems. the network simplex method.
Interior point methods for Linear Programming problems: main features and convergence conditions. 
Integer Linear programming: Knapsack Problem, Travelling Salesman Problem, Bin-Packing problem. Formulations and main characteristics.

Objectives

D1 - Knowledge and understanding
1. Master the main theoretical aspects in network optimization 
2. Know the fundamental aspects of the interior point algorithms for Linear Programming (LP) problems. 
3. Know the main characteristics of specific Integer Linear Programming (ILP).

D2 - Applying knowledge and understanding
1.To know the most important algorithms for network optimization problems. 
2. Address the issues related to post-optimality in Linear Programming 
3. Model Integer Linear Programming Problems

D3 - Making judgements
1 . Interpret the information from the solution of LP, ILP, and network optimization problems.
2. Evaluate different modelling techniques based on graphs, choose the best solution algorithms and and identify strengths and weaknesses.

D4 - Communication skills
1. Discuss the main aspect (optimality, duality, algorithms) for network flow optimization and ILP.

D5 - Learning skills
1 Study independently the most recent algorithmic developments in the area.
2. Deepen the theoretical and algorithmic aspects in in post-optimality for Linear Programming.
3. Deepen the theoretical and algorithmic aspects in network optimization 

Prerequisites

Linear Algebra
Vector and matrix operations
Solution of systems of linear equations
Linear programming

Teaching Methods

The course consists of lectures and laboratory work. In particular, the laboratory will be devoted to the formulation and solution of network optimization problems.

Verification of learning

The final evaluation consists of a oral exam. The oral exam is oriented to the verification of knowledge and skills acquired in the theoretical and algorithmic aspects of network optimization, sensitivity analysis and special ILPs.

Examination sessions are provided in June/July, September/October and February. The exams scheduled in Decemb

Texts

F.S. Hillier, G.J. Lieberman Ricerca Operativa, nona edizione, McGraw--Hill 2010
R.K. Ahuja, T.L. Magnanti, J.B. Orlin Network flows: theory, algorithms, and applications Prentice Hall, 1993
S. Wright Primal--Dual Interior--Point Methods SIAM, 1996.
L. A. Wolsey, G.L. Nemhauser, Integer and Combinatorial, Optimization, Wiley 1999 (Chapter II.2)

Latest News