00884 - Operations Research

Learning outcomes

The student will be able to define logic and mathematical models of optimization and decision problems by using mathematical programming and graph theory. He will be able to analyze the complexity of problems and characterize their difficulty. He will be able to solve and interpret some optimization problems also suing the personal computer.

Course contents

1. Introduction: Decision and Optimization problems. Models of Decision and Optimization problems and their classification. Methodology of Operations Research. Exact and Heuristic Algorithms. Brief introduction to computational complexity of problems and algorithms.
2. Graph Theory. Introduction and definitions. Shortest Spanning Tree Problem: Prim and Kruskal algorithms. Shortest Path Problem: Dijkstra algorithm. Introduction of more complex problems (Max flow on a network ,Travelling salesman, vehicle routing...).
3. Linear Optimization. Introduction to convex optimization problems. Canonic and Standard Forms of a linear optimization problem. Admissible and Basic solutions. Simplex algorithm in geometric and algebraic forms: optimality criteria, pivoting, degeneracy, two phases method for initial basis determination. Tableau form. Sensitivity Analysis. Introduction to the use of a solver package.
4. Integer Linear Optimization. Formulations of an integer linear optimization problems. Graphical solution. Branch and bound method basic principles. Introduction to traditional heuristic methods and to metaheuristics. Introduction of models and algorithms for specific applications (vehicle routing, cutting and packing, network design …)
5. Duality theory and dual simplex algorithm.
6. Decision analysis methods
   

Readings/Bibliography

slides available online

(to integrate the slides only)

S. MARTELLO, D. VIGO,,
ESERCIZI DI RICERCA OPERATIVA, PROGETTO LEONARDO, BOLOGNA, 1999.

S. MARTELLO,
LEZIONI DI RICERCA OPERATIVA, PROGETTO LEONARDO, BOLOGNA, 2002

M. FISCHETTI,
LEZIONI DI RICERCA OPERATIVA, EDIZIONI LIBRERIA PROGETTO, PADOVA, 1995

M. Dell'Amico,
120 esercizi di ricerca operativa, Bologna, Pitagora, 1996

S. Pallottino, A. Sciomachen (a cura di)
Scienza delle Decisioni per i Trasporti, Franco Angeli, 1999.

Assessment methods

written and oral compulsory tests

Links to further information

http://or.ingce.unibo.it

Office hours

See the website of Daniele Vigo