Contents
Network optimization: shortest path problems, maximum flow problem, and minimum cost flow problem: formulation, optimality algorithms.
The simplex method for network optimization problems.
Transportation and Assignment problems.
Integer Linear Programming. Totally Unimodular matrices and network optimization problems
Objectives
D1 - Knowledge and comprehension skills
Expected results:
1 Master the main theoretical tools for network optimization problems
2. Know the main characteristics of specific linear programming problems on graphs
D2 - Ability to apply knowledge and understanding
Expected results:
1 Know the main algorithms for network optimization problems.
2 Modeling Linear Programming problems on graphs
D3 - Autonomy of judgment
Expected results:
1 Interpret the information obtained by solving a network optimizaion problem.
2 Evaluate different modeling techniques based on graphs and choose specific algorithms and identify their strengths and weaknesses.
D4 - Communication skills
Expected results:
1 Discuss the main aspects (feasibility, optimality, etc.) related to network optimization.
D5 - Learning skills
Expected results:
1 Independently study recent algorithmic developments in the area.
2. To deepen the theoretical and algorithmic aspects of network optmization.
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.
A project may be assigned.
Examination sessions are provided in June/July, September/October and February. The exams scheduled in November/December and March are reserved to "Fuori Corso"
Texts
Class notes will be available.
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)

