Contents
Sensitivity and parametric analysis. Post-optimal analysis.
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)
