Operation Research (the English translation of "Ricerca operativa")
Teacher
prof. Paolo SERAFINI
Credits
6 CFU
Language
Italian
Objectives
Operations Research deals with efficient management problems via a mathematical and algorithmic approach. The course aims at giving the student both the basic tools to design a viable mathematical model of a real problem and the necessary understanding of the mathematical and algorithmic properties of the models, with a special emphasis to linear programming. Several examples will be provided toward this goal. Most models will be solved by using Excel or other linear programming packages.
Acquired skills
No available
Lectures and exercises (topics and specific content)
(48 hours)
Introduction to linear programming; general modelling issues, constraint identification, soft and hard constraints; objective identification; objectives and constraints; explicit objectives; pareto optima; example of the diet problem, modelling via linear programming; sensitivity analysis; identification of further objectives; efficient frontier identification; integrality constraints; model refinement.
Linear programming properties: geometric structure; vertices and basis solution; dual problem; complementarity; overview of simplex method; overview of branch-and-bound methods for integer variables.
Routing models: dynamic programming; optimality principle; recursive equation shortest paths (Bellman-Ford, Dijkstra, Floyd-Warshall).
Routing models with capacities: capacitated shortest paths, network flow problems; minimum cost flows; max flow; minimum cuts; examples of applications to electoral seat assignement.
Routing models with constraints on nodes or arcs: travelling salesman problem (cutting plane formulation). Eulerian circuits. Minimal spanning trees (Kruskal and Prim algorithms).
Allocation models: assignment; matching; example of applications to sport events; knapsack; bin packing; staffing models; LP with column generation, cutting stock, max flow, crew scheduling; vehicle routing problems; staffing problems.
Scheduling: infinite resource scheduling, PERT; finite resource scheduling, one machine problems, parallel machine problems, flow-shop, job-shop and open-shop; periodic scheduling.
References
- Paolo Serafini, Ricerca Operativa, Springer, 2009
- Paolo Serafini, Ottimizzazione, Zanichelli, Bologna 2000
- L. Schrage, LINDO: An optimization modeling system, Palo Alto Scientific Press, 1991
Type of exam
Oral examination with possibility of presenting and discussing a small project
Additional material or information on line