54681 - Principles of Operational Research

Learning outcomes

At the end of this course the student is capable of defining logic-mathematical models pf optimization and decision models, by using mathematical programming and graph theory. He or she can analyze the complexity of computational problems and characterize its difficulty. He or she can obtain, also by using computers, and interpret the solution of some classes of problems. The student is capable of writing a technical report and of appropriately exposing its contents.

Course contents

The course illustrates the main methodological tools proposed by the Operations Research for the solution of decision and optimization problems arising in industrial and management applications.

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. Duality theory: Definition of Primal-Dual pair. Weak and Strong Duality theorems and complementarity slackness conditions. Dual simplex algorithm. Sensitivity analysis.
5. 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 …)

 

Readings/Bibliography

Teaching methods

The course includes lectures and exercises in classroom with the teacher and free exercises in laboratory.

 

Assessment methods

Written and oral exams

Teaching tools

lecture notes available on internet

Links to further information

http://or.ingce.unibo.it

Office hours

See the website of Daniele Vigo