Course teached as: B000072 - FONDAMENTI DI RICERCA OPERATIVA 3-years First Cycle Degree (DM 270/04) in COMPUTER ENGINEERING
Teaching Language
Italian
Course Content
Introduction to optimization models and to Linear Programming (with both continuous and discrete variables). Theory and main algorithms for the solution of linear optimization problems, possibly involving also integer variables. Theory and main algorithms for network flow prroblems.
To be able to formulate optimization models to address practical problems.
To be able to analytically solve small linear optimization problems, possibly with integer variables or with network constraints.
Knowledge of the main algorithms and theoretical results for linear optimization, possibly with also integer variables or with network constraints.
Prerequisites
Linear Algebra: vectors, matrices, determinant, linear systems of equations.
Teaching Methods
Front teaching.
Further information
Type of Assessment
Written or oral examination consisting of:
- theoretical questions to verify the knowledge of simple mathematical programming models and of the theoretical bases of algorithms for LP, ILP and for graph models;
- practical exercises to verify the knowledge of algorithms for LP, ILP and for graph models.
Course program
1. Linear Optimization
Introduction to the modeling approach and formulation of simple Linear Programming models.
Introduction to Linear Porgramming (LP). Standard Form of an LP problem:
solution, bases, basic feasible solutions; geometric interpretation of bases.
The Fundamental Theorem of LP. Geometry of LP.
Simplex method - matrix formulation.
Duality theory; definition of dual problems; duality theorems;
interpretation of the dual problem; complementary slackness;
dual simplex method.
Sensitivity analysis: sensitivity on the right hand side; sensitivity on cost
coefficients; adding a variable or a constraint.
2. Integer Linear Programming (ILP)
Examples of ILP problems and models.
Links between LP and ILP.
General purpose methods for ILP: cutting plane methods (Gomory), Branch and Bound.
3. Network Flows
Bases and basic solutions. Network flow problems.
Shortest paths: Disjkstra algorithm. Maximum flow problem: method of Ford and Fulkerson. Maximum flow /
minimum cut theorem.